Pagini recente » Cod sursa (job #1773421) | Cod sursa (job #1776171) | Cod sursa (job #2025940) | Cod sursa (job #786575) | Cod sursa (job #2370069)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000005;
int p[NMAX];
char A[NMAX];
char B[NMAX];
int v[NMAX];
int main()
{
fin >> (A+1);
int n=strlen(A+1);
fin >> (B+1);
int m=strlen(B+1);
p[1]=0;
int q;
for(int i=2;i<=n;i++)
{
q=p[i-1];
while(A[q+1]!=A[i] and q!=0)
{
q=p[q];
}
if(A[q+1]!=A[i]) p[i]=0;
else p[i]=q+1;
}
q=0;
int rasp=0;
for(int i=1;i<=m;i++)
{
while(A[q+1]!=B[i] and q!=0)
q=p[q];
if(A[q+1]==B[i]) q++;
if(q==n)
{
q=p[q];
v[++rasp]=i-n;
}
}
fout << rasp << '\n';
rasp=min(rasp,1000);
for(int i=1;i<=rasp;i++)
{
fout << v[i] << ' ';
}
return 0;
}