Cod sursa(job #1347172)

Utilizator BologaDragosBologa Dragos BologaDragos Data 18 februarie 2015 20:26:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char P[2000002] ;

int v[1003] ;

char T[2000002] ;

int L[2000003] ;

int n,k,p,t ;

int main()
{

    int i,m,ct=0 ;
    f.getline(P,sizeof(P)) ;
    f.getline(T,sizeof(T)) ;

    m=strlen(P) ;
    n=strlen(T) ;

    L[1]=0 ;
    k=0 ;
    for(p=2;p<=m;p++)
    {
        while(k!=0&&P[k]!=P[p-1])
            k=L[k] ;
        if(P[k]==P[p-1])
            k++ ;
        L[p]=k ;
    }
    k=0 ;

    for(t=1;t<=n;t++)

    {
        while(k!=0&&P[k]!=T[t-1])
            k=L[k] ;
        if(P[k]==T[t-1])
            k++ ;
        if(k==m)
        {
            ct++ ;
            v[ct]=t-m ;
            k=L[k] ;
        }
    }

    g<<ct<<'\n' ;
    for(i=1;i<=ct&&i<=1000;i++)
        g<<v[i]<<" " ;



    return 0;
}