Cod sursa(job #1174258)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 22 aprilie 2014 14:16:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>

using namespace std;

int i,q,nr_sol,n,m;

int sol[2000005],p[2000005];

char A[2000005],B[2000005],C[2000005];

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.get(B,2000005);
    f.get();
    f.get(A,2000005);
    n=strlen(A);m=strlen(B);
    strcpy(C,A);
    strcpy(A+1,C);
    strcpy(C,B);
    strcpy(B+1,C);
    p[1]=0;
    for(i=2;i<=m;i++) {
        q=p[i-1];
        while(B[i]!=B[q+1] && q!=0)
            q=p[q];
        if(B[i]==B[q+1])
            p[i]=q+1;
        else
            p[i]=0;
    }
    q=0;
    for(i=1;i<=n;i++) {
        while(A[i]!=B[q+1] && q!=0)
            q=p[q];
        if(A[i]==B[q+1])
            q++;
        if(q==m) {
            nr_sol++;
            sol[nr_sol]=i-m;
            q=p[q];
        }
    }
    g<<nr_sol<<"\n";
    for(i=1;i<=1000 && i<=nr_sol;i++)
        g<<sol[i]<<" ";
    return 0;
}