Cod sursa(job #1650413)

Utilizator ZenusTudor Costin Razvan Zenus Data 11 martie 2016 18:09:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#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;
}