Needle in the haysack

help
,
1

Question

#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vc vector<char>
#define vii vector<vi>
#define mp make_pair
#define vpi vector< pair<int, int> >
#define take_input freopen("input.txt", "r", stdin)
#define give_output freopen("output.txt", "w", stdout)
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fi first
#define se second
#define mod 1000000007
#define min_pql priority_queue< int, vector<int>, greater<int> >

using namespace std;
using namespace std::chrono;

struct KMP{
    string s;
    int *lps;

    KMP(string s){
        this->s = s;
        int n = s.length();
        lps = new int[n+1];
    }
    
    // finding lps array
    int* LPS(string s){
        int n = s.length();
        lps[0]=0;
        for(int i=1; i<=n; i++){
            int j=lps[i-1];
            while(j>0 && s[i] != s[j]){
                j = lps[j-1];
            }
            if(s[i]==s[j]) j++;
            lps[i]=j;
        }
        return lps;
    }
    
    // kmp algorithm
    void kmp(string s, string p){
        int *lps = LPS(s);
        int m = p.length();
        int n = s.length();
        int j=0;
        int i=0;
        vector<int> ans;
        while(i<n && j<m){
            if(s[i] == p[j]) {
                i++; j++;
                if(j==m){
                	ans.push_back(i-j);
                	while(j>0){
                		i = i-lps[j-1];
                    	j=lps[j-1];
                    }
                    continue;
                }
            }else{
                if(j>0) j = lps[j-1];
                else i++;
            }
        }
		for(int i:ans) cout << i << endl;  
		if(ans.empty()) cout << endl;      
    }
};

int32_t main(){
    fastIO;
    // take_input;
    // give_output;
    // write code
    int n;
    while(cin >> n){
    	// cout << n << endl;
    	string s, t;
    	cin >> t >> s;
    	KMP new_obj(s);
    	new_obj.kmp(s, t);
    }
}

I am getting WA for this. I used simple kmp algorithm but can’t get where I am going wrong

2 
3
bba
bbbaabb

appears to send your code into an infinite loop. I think that’s a valid testcase (?)

1 Like
3

Yeah
I got my mistake
Thanks

1 Like