KMP Algorithm

#include <bits/stdc++.h>
using namespace std;

		
vector<int> lps_table(const string &pattern) {
    // Your code goes here
    int n = pattern.length();
    vector<int> lps(n, 0);
    for(int i = 1; i < n; i++) {
        int j = lps[i - 1];
        while(j > 0 && pattern[i] != pattern[j])
        j = lps[j - 1];
        if(pattern[i] == pattern[j])
        j++;
        lps[i] = j;
    }
    return lps;
}


int main() {
	// your code goes here
	string text, pattern;
	getline(cin, text);
	getline(cin, pattern);
	cout << text << endl;
	cout << pattern << endl;
	vector<int> lps = lps_table(pattern);
	int i = 0; 
	int j = 0; 
	while(i < text.length()) {
	    if(text[i] == pattern[j]) {
	        i++;
	        j++;
	    }
	    else {
	        if(j > 0)
	        j = lps[j - 1];
	        else 
	        i++;
	    }
	    if(j == pattern.length()) {
	        cout << i - j << endl;
	        j = lps[j - 1];     // To print only 1 occurence replace this line with break
	    }
	}
	return 0;
}