Pagini recente » Cod sursa (job #624971) | Cod sursa (job #2307066) | Cod sursa (job #297464) | Cod sursa (job #1574000) | Cod sursa (job #2263805)
#include<cstdio>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int NMAX=2000005;
int T[NMAX];
queue<int> indx;
string pat,txt;
void precomp(){
int i=1,j=0;
while(i<(int)pat.length()){
if(pat[i]==pat[j]){
T[i]=j+1;
i++,j++;
}
else
if(j!=0){
while(j!=0 && pat[i]!=pat[j])
j=T[j-1];
}
else
i++;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i=0,j=0,sol=0;
cin>>pat>>txt;
txt.push_back('.');
precomp();
while(i<=(int)txt.length()){
if(j>=(int)pat.length()){
if(indx.size()<1000)
indx.push(i-pat.length());
sol++;
j=T[j-1];
}
if(txt[i]==pat[j])
i++,j++;
else
if(j!=0)
j=T[j-1];
else
i++;
}
printf("%d\n", sol);
while(!indx.empty()){
printf("%d ", indx.front());
indx.pop();
}
return 0;
}