Pagini recente » Cod sursa (job #2222873) | Cod sursa (job #1355282) | Cod sursa (job #1701293) | Cod sursa (job #1595463) | Cod sursa (job #2425038)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, nsol;
int pi[2000002];
char txt[2000002], pat[2000002];
int sol[1001];
void make_prefix()
{
pi[1]=0;
int k=0;
for(int q=2; q<=m; ++q)
{
while(k>0 && pat[k+1]!=pat[q]) k=pi[k];
if(pat[k+1]==pat[q]) ++k;
pi[q]=k;
}
}
int main()
{
fin>>(pat+1);
fin>>(txt+1);
m=strlen(pat+1);
n=strlen(txt+1);
make_prefix();
int q=0;
for(int i=1; i<=n; ++i)
{
while(q>0 && txt[i]!=pat[q+1]) q=pi[q];
if(txt[i]==pat[q+1]) ++q;
if(q==m)
{
q=pi[m];
++nsol;
if(nsol<=1000) sol[nsol]=i-m;
}
}
fout<<nsol<<"\n";
for(int i=1; i<=min(nsol, 1000); ++i) fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}