Pagini recente » Cod sursa (job #739808) | Cod sursa (job #1141917) | Cars | Cod sursa (job #948235) | Cod sursa (job #1650413)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2000009;
int phi[nmax] , is[nmax];
char a[nmax] , b[nmax];
int i , n , m , k , S;
int main()
{
freopen("strmatch.in" , "r" , stdin);
freopen("strmatch.out" , "w" , stdout);
gets(a + 1);
n = strlen(a + 1);
gets(b + 1);
m = strlen(b + 1);
phi[1] = k = 0;
for (i = 2 ; i <= n ; ++i)
{
while (k && a[k + 1] != a[i]) k = phi[k];
if (a[k + 1] == a[i]) k++;
phi[i] = k;
}
k = 0;
for (i = 1 ; i <= m ; ++i)
{
while (k && a[k + 1] != b[i]) k = phi[k];
if (a[k + 1] == b[i]) k++;
if (k == n) is[++S] = i - n;
}
printf("%d\n" , S);
for (i = 1 ; i <= 1000 && i <= S ; ++i)
printf("%d " , is[i]);
printf("\n");
return 0;
}