Pagini recente » Cod sursa (job #870129) | Cod sursa (job #786074) | Cod sursa (job #485020) | Cod sursa (job #2085377) | Cod sursa (job #2239853)
#include <iostream>
#include <fstream>
#include <vector>
const int MAXN = 2000005;
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int lps[MAXN],n,m;//Longest prefix and suffix of pattern [0...i] #geeksforgeeks
string text,pattern;
vector<int>ans;
void LPS_generator(){
int i = 1,j = 0;
while(i < m){
if(pattern[i] == pattern[j]){
j++;
lps[i] = j;
i++;
}else{
if(j)
j = lps[j - 1];
else{
lps[i] = 0;
i++;
}
}
}
}
void KMP(){
int i = 0,j = 0;
while(i < n){
if(text[i] == pattern[j]){
j++;
i++;
if(j == m){
ans.push_back(i - j);
j = lps[j - 1];
}
}else{
if(j)
j = lps[j - 1];
else
i++;
}
}
}
int main()
{
in>>pattern>>text;
n = text.size(),m = pattern.size();
LPS_generator();
KMP();
out<<ans.size()<<"\n";
for(int i = 0; i < ans.size() && i < 1000; i++)
out<<ans[i]<<" ";
return 0;
}