Cod sursa(job #2038412)

Utilizator ImbuzanRaduImbuzan Radu ImbuzanRadu Data 13 octombrie 2017 17:42:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
char N[200000],H[200000],c;
int h,n,S[200000],aux[10000];
int f,k,cont;

ifstream fi("strmatch.in");
ofstream g("strmatch.out");

int main()
{
    fi>>N+1>>H+1;
    n=strlen(N+1);
    h=strlen(H+1);

    S[0]=-1;
    S[1]=0;
    for(int i=2;i<=n;i++){
        k=i-1;
        c=N[i];
        while(S[k]!=-1 && N[S[k]+1]!=c)
            k=S[k];
        S[i]=S[k]+1;
    }

    for(int i=1;i<=h;i++){
        while(f!=-1)
            if(N[f+1] == H[i])
                break;
            else f=S[f];
        if(f==-1)
            f=0;
        else {
            f++;
            if(f==n){
                cont++;
                aux[cont]=i-f;
                f=S[f];
            }
        }
    }
    g<<cont<<"\n";
    for(int i=1;i<=cont;i++)
        g<<aux[i]<<" ";
    return 0;
}