Search Pattern (KMP-Algorithm) | Strings | HARD

[@galepraveen]

vector search(string& pat, string& txt) {
int n = pat.size(), m = txt.size();

vector lps(n, 0);
int length = 0;
int i = 1;

// 1. Generating LPS array
while(i < n){
if(pat[i] == pat[length]){
length += 1;
lps[i] = length;
i += 1;
}else{
if(length > 0){
length = lps[length - 1];
}else{
i += 1;
}
}
}

// 2. Matching Pattern
vector res;

i = 0;
int j = 0;
while(j < m){
if(txt[j] == pat[i]){
i += 1;
j += 1;
}else{
if(i > 0){
i = lps[i - 1];
}else{
j += 1;

}
}

if(i == n){
res.push_back(j - i);

i = lps[i - 1];
}
}

return res;
}