Pagini recente » Cod sursa (job #656352) | Cod sursa (job #108141) | Cod sursa (job #159186) | Cod sursa (job #197813) | Cod sursa (job #2782850)
#include <bits/stdc++.h>
using namespace std;
#define dim 2000001
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[dim],b[dim];
int v[1001],p[dim];
int k,t;
int main()
{
ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
fin>>a;
fin>>b;
int m = strlen(a);
int n = strlen(b);
for(int i = 2;i<m;++i)
{
while(k && a[k+1] != a[i])
k = p[k];
if(a[k+1] == a[i])
k++;
p[i] = k;
}
int i;
for(k = 0,i=1;i<n;i++)
{
while(k && a[k+1] != b[i])
k=p[k];
if(a[k+1] == b[i])
k++;
if(k == m-1 && a[0] == b[i-k])
{
if(t < 1000)
v[t] = i-m+1;
t++;
}
}
for(fout<<t<<'\n', t=t>1000?1000:t, i=0;i<t;++i)
fout<<v[i]<<" ";
fin.close();
fout.close();
return 0;
}