Cod sursa(job #1944007)

Utilizator Liviu_Ionut_MoantaMoanta Ionut Liviu Liviu_Ionut_Moanta Data 28 martie 2017 21:55:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("oite.in");
ofstream fout("oite.out");
int n,m,i,j,k;
int q[2000005],sol[2000005];
char s1[2000005],s2[2000005];
int main(){
    fin>>s1;
    fin>>s2;
    n=strlen(s1);
    m=strlen(s2);
    for(i=1;i<n;i++){
        while(k>0&&s1[i]!=s1[k]){
            k=q[k-1];
        }
        if(s1[i]==s1[k]){
            k++;
        }
        q[i]=k;
    }
    k=0;
    for(i=0;i<m;i++){
        while(k>0&&s2[i]!=s1[k]){
            k=q[k-1];
        }
        if(s2[i]==s1[k]){
            k++;
        }
        if(k==n){
            k=q[n-1];
            sol[++j]=i-n+1;
        }
    }
    fout<<j<<"\n";
    for(i=1;i<=j;i++){
        fout<<sol[i]<<" ";
    }
    return 0;
}