Cod sursa(job #1970984)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 19 aprilie 2017 19:03:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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);
    int n=strlen(s);
    int m=strlen(k);
    for(int i=n;i>=1;i--)
    {
        s[i]=s[i-1];
    }
    for(int i=m;i>=1;i--)
    {
        k[i]=k[i-1];
    }
    s[0]=' ';
    k[0]=' ';
    s[n+1]=NULL;
    k[m+1]=NULL;
}

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

int c=0;

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

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;
}