Pagini recente » Cod sursa (job #2325820) | Cod sursa (job #1295605) | Cod sursa (job #373649) | Cod sursa (job #1700625) | Cod sursa (job #1376672)
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000001;
char A[Nmax],B[Nmax];
int pi[Nmax],ans[1001],N,M;
int main(){
in.getline(A,Nmax); N=strlen(A);
in.getline(B,Nmax); M=strlen(B);
int w=0;
for(int i=1;i<N;i++){
while(w && A[w]!=A[i]) w=pi[w-1];
if(A[w]==A[i]) w++;
pi[i]=w;
}
w=0;
for(int i=0;i<M;i++){
while(w && A[w]!=B[i]) w=pi[w-1];
if(A[w]==B[i]) w++;
if(w==N){
if(ans[0]<1000) ans[++ans[0]]=(i-N+1);
else ans[0]++;
}
}
out<<ans[0]<<'\n';
for(int i=1;i<=min(1000,ans[0]);i++) out<<ans[i]<<' ';
return 0;
}