Pagini recente » Cod sursa (job #1517724) | Cod sursa (job #2257494) | Cod sursa (job #879742) | Cod sursa (job #2064497) | Cod sursa (job #1374513)
#include <fstream>
#include <cstring>
#define max_dim 2000010
using namespace std;
int nxt[max_dim], positions[1010];
char a[max_dim], b[max_dim];
int n, m, i, q, k;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a+1; n=strlen(a+1);
f>>b+1; m=strlen(b+1);
q=0;
nxt[1]=0;
for(i=2; i<=n; i++)
{
while(a[i]!=a[q+1] && q!=0)
q=nxt[q];
if(a[i]==a[q+1])
++q;
nxt[i]=q;
}
q=0;
for(i=1; i<=m; i++)
{
while(b[i]!=a[q+1] && q!=0)
q=nxt[q];
if(b[i]==a[q+1])
q++;
if(q==n)
{
k++;
if(k<=1000) positions[k]=i-n;
q=nxt[q];
}
}
g<<k<<"\n";
if(k>1000) k=1000;
for (i=1; i<=k; i++)
g<<positions[i]<<" ";
return 0;
}