Cod sursa(job #1206217)

Utilizator mariusn01Marius Nicoli mariusn01 Data 9 iulie 2014 10:54:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>
#define DIM 2000010

using namespace std;


int P[DIM], S[1010];
char A[DIM], B[DIM];
int n, m, i, q, k;

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin>>A+1; n = strlen(A+1);
    fin>>B+1; m = strlen(B+1);

    // preprocesare pentru A: A[i] = lungimea maxima a unui sufix al lui A terminat pepozitia i
    // care e in acelasi timp prefix (lungime < i)
    q = 0;
    P[1] = 0;
    for (i=2;i<=n;i++) {
        // calcule P[i]
        while (A[i] != A[q+1] && q!=0)
            q = P[q];

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

        P[i] = q;
    }

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

        if (q == n) {
            k++;
            if (k<=1000)
                S[k] = i-n;
            q = P[q];
        }
    }
    fout<<k<<"\n";
    if (k > 1000)
        k = 1000;

    for (i=1;i<=k;i++)
        fout<<S[i]<<" ";

    return 0;
}