Cod sursa(job #1338949)

Utilizator mariusn01Marius Nicoli mariusn01 Data 10 februarie 2015 16:03:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>

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

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

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

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

        if (A[i] == A[L+1]) {
            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-n+1;
            }
            L = P[L];
        }
    }

    fout<<nr<<"\n";
    if (nr > 1000)
        nr = 1000;
    for (i=1;i<=nr;i++)
        fout<<S[i]-1<<" ";
    return 0;
}