Cod sursa(job #1685720)

Utilizator andrei232000Andrei Maria andrei232000 Data 11 aprilie 2016 20:19:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000001], B[2000001];
int l, i, j, ls, N;
int v[1001];
int pi[2000001];
int main()
{
    fin>>A;
    fin>>B;
    l = strlen(A);
    for(i = 1; i < l; i++)
    {
        while(j && A[j] != A[i])
        {
            j = pi[j - 1];
        }
        if(A[i] == A[j])
        {
            j++;
        }
        pi[i] = j;
    }
    ls = strlen(B);
    j = 0;
    for(i = 0; i < ls; i++)
    {
        while(j && A[j] != B[i])
        {
            j = pi[j - 1];
        }
        if(A[j] == B[i])
        {
            j++;
        }
        if(j == l)
        {
            j = pi[l - 1];
            if(N < 1000)
            {
                v[N] = i - l + 1;
            }
            N++;
        }
    }
    fout<<N<<'\n';
    if(N > 1000)
    {
        N = 1000;
    }
    for(i = 0; i < N; i++)
    {
        fout<<v[i]<<" ";
    }
    return 0;
}