Pagini recente » Istoria paginii runda/cercel_e_gay | Cod sursa (job #1537105) | Cod sursa (job #2887655) | Cod sursa (job #2927621) | Cod sursa (job #2803284)
#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';
for(i=1; i<=nr; i++)
{
fout<<rez[i]<<" ";
}
}
int main()
{
fin>>(pat+1);
fin.get();
fin>>(s+1);
kmp();
return 0;
}