Cod sursa(job #1339140)

Utilizator mariusn01Marius Nicoli mariusn01 Data 10 februarie 2015 18:17:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <cstring>

using namespace std;

char A[2000010], B[2000010];
int P[2000010], i, S[1010], n, m, nr, L;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int main() {
    fin>>A+1;
    n = strlen(A+1);
    fin>>B+1;
    m = strlen(B+1);

    P[1] = 0;
    L = 0;

    for(i=2; i<=n; i++){

        while(L!=0 && A[L+1]!=A[i])
            L=P[L];

        if(A[L+1] == A[i])
            L++;

        P[i] = L;

    }

    L = 0;
    for (i=1;i<=m;i++) {
        while (L && B[i]!= A[L+1])
            L = P[L];

        if (B[i] == A[L+1])
            L++;

        if (L == n) {
            nr ++;
            if (nr <= 1000)
                S[nr] = i-L+1;
            L = P[L];

        }

    }

    fout<<nr<<"\n";
    if (nr > 1000)
        nr = 1000;

    for (i=1;i<=nr;i++)
        fout<<S[i]-1<<" ";
    return 0;
}