Pagini recente » Cod sursa (job #2637071) | Cod sursa (job #2811028) | Cod sursa (job #1928981) | Cod sursa (job #1207406) | Cod sursa (job #489262)
Cod sursa(job #489262)
// infoarena: problema/strmatch //
#include <fstream>
#include <cstring>
#define MAXN 2000100
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[MAXN],b[MAXN];
int i,j,n,m,l[MAXN],k,q,r[MAXN];
int main()
{
in>>a>>b;
n = strlen(a);
m = strlen(b);
l[0] = 0;
for(i=1; i<n; i++)
{
while(k>0 && a[k] != a[i])
k = l[k];
if(a[k] == a[i])
k++;
l[i] = k;
}
k=0;
for(i=0; i<m; i++)
{
while(k>0 && a[k] != b[i])
k=l[k-1];
if(a[k] == b[i])
k ++;
if(k == n)
{
r[++q] = i-n+1;
k = l[k-1];
}
}
out<<q<<'\n';
for(i=1; i<=q; i++)
out<<r[i]<<' ';
return 0;
}