Pagini recente » Cod sursa (job #191414) | Cod sursa (job #1911817) | Cod sursa (job #1020811) | Cod sursa (job #20666) | Cod sursa (job #1364547)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000002],sir2[2000002];
int pi[2000002];
void Prelucrare(char t[2000002],int pi[2000002])
{ int i,m=strlen(t);int k;
pi[0]=0;k=0;
for(i=1;i<=m;i++)
{ if(t[i]==t[k]) k++;
else {while(k>0&&t[k]!=t[i]) k=pi[k-1];
if(t[k]==t[i]) k++;
}
pi[i]=k;
}
}
int z,poz[2000002];
void KMP(char s[2000002],char t[2000002])
{ int n=strlen(s),i,k=0,m=strlen(t);
for(i=0;i<n;i++)
{ if(s[i]==t[k]) k++;
else { while(k>0&&t[k]!=s[i]) k=pi[k-1];
if(t[k]==s[i]) k++;
}
if(k==m) {z++;poz[z]=i-m+1;}
}
}
int main()
{ fin.get(sir1,2000002);fin.get();
fin.get(sir2,2000002);
Prelucrare(sir1,pi);
KMP(sir2,sir1);
fout<<z<<"\n";
int i;
if(z>=1000)
for(i=1;i<=1000;i++)
fout<<poz[i]<<" ";
else for(i=1;i<=z;i++)
fout<<poz[i]<<" ";
return 0;
}