Cod sursa(job #1075754)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 9 ianuarie 2014 15:33:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<cstring>
#define dim 2000003
using namespace std;
 
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[dim],B[dim];
int i,j,n,m,sol,a[1040];
int k,p[dim];
int main () {
 
    f>>(A+1);
    f>>(B+1);
 
    p[k]=0;
    n=strlen(A+1);
    m=strlen(B+1);
    for(i=2;i<=n;++i) {
 
        while(k>0 && A[k+1]!=A[i]){
            k=p[k];
        }
 
        if(A[i]==A[k+1])
            k++;
        p[i]=k;
    }
    k=0;
    for(i=1;i<=m;++i){
 
        while(k>0  && A[k+1]!=B[i])
            k=p[k];
 
        if(A[k+1]==B[i]){
            ++k;
        }
        if(k==n){
 
            sol++;
            if(sol<=1000){
                a[sol]=i-k;
            }
        }
 
    }
    g<<sol<<"\n";
    if(sol>=1000)
        sol=1000;
    for(i=1;i<=sol;++i){
        g<<a[i]<<" ";
    }
    return 0;
}