Cod sursa(job #1213455)

Utilizator mihaimusatMihai Musat mihaimusat Data 28 iulie 2014 10:51:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>
#define NMAX 200005

using namespace std;

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

int i,sol,m,n,s[NMAX],p[NMAX],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;
}