Cod sursa(job #1230590)

Utilizator andreey_047Andrei Maxim andreey_047 Data 18 septembrie 2014 17:25:45
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define nmax 2000001
using namespace std;
char A[nmax],B[nmax];
int pi[nmax],n,m,nr,poz[nmax];
void prefix(){
   int i,q=0;
 for(i=2;i<=n;i++){
    while(q && A[q+1] != A[i])
        q = pi[q];
    if(A[q+1] == A[i])
        q++;
    pi[i] = q;
    pi[1]=0;
 }
}
int main(){
    int q=0,i;
    ifstream fin("strmatch.in");
    fin>>A+1>>B+1;
    fin.close();
    n=strlen(A+1);
    m = strlen(B+1);
   prefix();
    for(i = 2; i <= m; i++){
        while(q && A[q+1] != B[i])
            q=pi[q];
        if(A[q+1] == B[i])
           q++;
       if(q == n){
            nr++;
            q = pi[q];
            poz[nr] = i-n;
       }
    }
 ofstream fout("strmatch.out");
    fout << nr<<'\n';
    if(nr >= 1000) nr = 1000;
    for(i=1;i<=nr;i++) fout << poz[i]<<' ';
    fout << '\n';
     fout.close();
return 0;
}