Cod sursa(job #1159027)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 29 martie 2014 11:34:22
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[2000005],B[2000005],C[2000005];

int i,sol,m,n,s[2000005],p[2000005],q;

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>B;
    f>>A;
    m=strlen(B);
    n=strlen(A);
    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[q+1]==B[i])
            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) {
            sol++;
            s[sol]=i-m;
            q=p[q];
        }
    }
    g<<sol<<"\n";
    for(i=1;i<=sol && i<=1000;i++)
        g<<s[i]<<" ";
    g<<"\n";
    return 0;
}