Pagini recente » Cod sursa (job #2747821) | Cod sursa (job #1244243) | Cod sursa (job #1707299) | Cod sursa (job #339503) | Cod sursa (job #2803293)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,nr,m;
int rez[2000005],urmator[2000005];
char s[2000005],pat[2000005];
void init()
{
int i,j;
urmator[1]=0;
j=0;
for(i=2; i<=n; i++)
{
while(j>0&&pat[i]!=pat[j+1])
j=urmator[j];
if(pat[i]==pat[j+1])j++;
urmator[i]=j;
}
}
;
void kmp()
{
n=strlen(pat+1);
m=strlen(s+1);
init();
urmator[0]=0;
int i,j;
int x;
j=0;
for(i=1; i<=m; i++)
{
while(s[i]!=pat[j+1]&&j>0)
j=urmator[j];
if(s[i]==pat[j+1])j++;
if(j>=n){rez[++nr]=i-n;}
}
fout<<nr<<'\n';
nr=min(nr,1000);
for(i=1; i<=nr; i++)
{
fout<<rez[i]<<" ";
}
}
int main()
{
fin>>(pat+1);
fin>>(s+1);
kmp();
return 0;
}