Pagini recente » Cod sursa (job #3163684) | Cod sursa (job #2628670) | Cod sursa (job #375355) | Cod sursa (job #2406390) | Cod sursa (job #2172080)
#include <bits/stdc++.h>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
vector<int> rasp;
void GeneratePrefixTable(string needle,int p[]){
int len=0;
p[0]=0;
int i=1;
int N=needle.length();
while(i<N){
if(needle[len]==needle[i]){
len++;
p[i]=len;
i++;
}
else if(len==0){
p[i]=0;
i++;
}
else{
len=p[len-1];
}
}
}
void KMP(string haysack,string needle){
int M=needle.length();
int p[M];
GeneratePrefixTable(needle,p);
int N=haysack.length();
int i=0,j=0;
while(i<N){
if(haysack[i]==needle[j]){
i++;
j++;
}
if(j==M){
//cout<<"Pattern found "<<i-j<<"\n";
rasp.push_back(i-j);
j=p[j-1];
}
else if(i<N&&haysack[i]!=needle[j]){
if(j>0){
j=p[j-1];
}
else{
i++;
}
}
}
}
int main(){
string needle;
string haysack;
in>>needle>>haysack;
KMP(haysack,needle);
out<<rasp.size()<<"\n";
for(auto r:rasp){
out<<r<<" ";
}
return 0;
}