Cod sursa(job #755190)

Utilizator visanrVisan Radu visanr Data 4 iunie 2012 22:24:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

#define nmax 2000012

char A[nmax], B[nmax];
int n, m, p, q, pi[nmax], pos[1020], cnt;

void prefix()
{
     int i, q = 0;
     pi[1] = 0;
     for(i = 2; i <= m; i++)
     {
           while(q && A[q + 1] != A[i]) q = pi[q];
           if(A[q + 1] == A[i]) ++q;
           pi[i] = q;
     }
}

void solve()
{
     int i;
     for(i = 1; i <= n; i++)
     {
           while(q && A[q + 1] != B[i]) q = pi[q];
           if(A[q + 1] == B[i]) q++;
           if(q == m)
           {
                q = pi[m];
                cnt++;
                if(cnt <= 1000) pos[cnt] = i - m;
           }
     }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s", A);
    scanf("%s", B);
    m = strlen(A);
    n = strlen(B);
    for(int i = m + 1; i; i--) A[i] = A[i - 1];
    for(int i = n + 1; i; i--) B[i] = B[i - 1];
    A[0] = B[0] = ' ';
    prefix();
    solve();
    printf("%i\n", cnt);
    for(int i = 1; i <= min(cnt, 1000); i++) printf("%i ", pos[i]);
    return 0;
}