Cod sursa(job #1015633)

Utilizator vasandANDREI POP vasand Data 24 octombrie 2013 21:43:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
# include <iostream>
# include <fstream>
# include <string.h>
# define nmax 2000000
using namespace std;

char s[nmax],n,m,w[nmax],f[nmax];
int nr;

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

void table()
{
    int i,j;
    f[0]=f[1]=0;

    for(i=2; i<=m; i++)
    {
        j=f[i-1];
        for( ; ; )
        {
            if(w[i-1]==w[j])
            {
                f[i]=j+1;
                break;
            }
            else
            {
               if(j==0)
               {
                   f[i]=0;
                   break;
               }
               j=f[j];
            }
        }
    }
}

void cauta()
{
    int i=0,j=0;
    while(j<=n)
    {
        if(w[i]==s[j])
        {
            i++;
            j++;
            if(i==m)
            {
                nr+=1;
                i=0;
                i=f[i];
            }
        }
        else
        {
            if(i>0)
                i=f[i];
            else
                j+=1;
        }
    }
}


int main()
{
    fin.getline(w,nmax);
    fin.getline(s,nmax);
    m=strlen(w);
    n=strlen(s);

    table();
    cauta();

    g<<nr<<'\n';

    return 0;
}