Pagini recente » Cod sursa (job #111865) | Cod sursa (job #3179703) | Cod sursa (job #1819622) | Cod sursa (job #2391681) | Cod sursa (job #1327759)
#include <fstream>
#include <string.h>
using namespace std;
fstream fin("strmatch.in", ios::in);
fstream fout("strmatch.out", ios::out);
#define MAX 2000010
char N[MAX], M[MAX];
int n, m, pi[MAX], d[1005];
void prefix()
{
int q=0;
pi[1]=0;
for(int i=2; i<=n; i++){
while(N[i]!=N[q+1] && q>0)
q=pi[q];
if(N[q+1]==N[i])
q++;
pi[i]=q;
}
}
void KMP()
{
int q=0;
pi[1]=0;
for(int i=2; i<=n; i++){
while(N[i]!=N[q+1] && q>0)
q=pi[q];
if(N[q+1]==N[i])
q++;
pi[i]=q;
}
q=0;
for(int i=1; i<=m; i++){
while(N[q+1]!=M[i] && q>0)
q=pi[q];
if(M[i]==N[q+1])
q++;
if(q==n)
d[++d[0]]=i-n;
}
}
int main()
{
fin.getline(N+1, MAX); ::n=strlen(N+1);
fin.getline(M+1, MAX); ::m=strlen(M+1);
KMP();
fout<<d[0]<<"\n";
for(int i=1; i<=d[0]; i++)
fout<<d[i]<<" ";
fin.close();
fout.close();
return 0;
}