Cod sursa(job #1970897)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 19 aprilie 2017 18:04:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <cstring>
#define nmax 2000002
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);
    fin.getline(s,nmax);
}

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

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)
        {
            c++;
            if(c>1000)
            {
                break;
            }
            else
            {
                v[c]=i-m;
            }
        }
    }
}

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

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