Cod sursa(job #1347186)

Utilizator BologaDragosBologa Dragos BologaDragos Data 18 februarie 2015 20:37:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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++ ;
            if(ct<=1000)
            v[ct]=t-m ;
            k=L[k] ;
        }
    }

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

    g<<'\n' ;

    return 0;
}