Cod sursa(job #1970955)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 19 aprilie 2017 18:51:55
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;

char s[nmax];
char k[nmax];
int t[nmax];
int v[1002];

void citire()
{
    std::fstream fin("strmatch.in",std::ios::in);
    fin.getline(k,nmax-1);
    fin.getline(s,nmax-1);
}

void temp_suffix_build()
{
    int i=1,j=0;
    for(int i=1;k[i]!=NULL;i++)
    {
        while((k[j]!=k[i])&&j)
        {
            j=t[j-1];
        }
        if(k[j]!=k[i])
        {
            t[i]=j;
        }
        else
        {
            t[i]=j+1;
        }
    }
}

int c=0;

void searcha()
{
    int i=0,j=0;
    int m=strlen(k);
    while(s[i]!=NULL)
    {
        if(s[i]==k[j])
        {
            i++;
            j++;
        }
        else
        {
            while(j&&s[i]!=k[j])
            {
                j=t[j-1];
            }
        }
        if(j==0&&s[i]!=k[j])
        {
            i++;
        }
        if(j==m)
        {
            j=v[j];
            c++;
            if(c<=1000)
            {
                v[c]=i-m;
            }
        }
    }
}

void afis()
{
    std::fstream fout("strmatch.out",std::ios::out);
    fout<<c<<"\n";
    for(int i=1;i<=min(c,1000);i++)
    {
        fout<<v[i]<<" ";
    }
}

int main()
{
    citire();
    temp_suffix_build();
    searcha();
    afis();
    return 0;
}