Cod sursa(job #2090909)

Utilizator veronicamicleVeronica Micle veronicamicle Data 18 decembrie 2017 20:32:54
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[2000001],d[2000001],n,m;
char s[2000001],v[2000001];
void prefix()
{
    int k;
    k=-1;
    pi[0]=-1;

    for(int i=1;i<=n;i++)
    {
        while(k>-1&&s[k+1]!=s[i])
        k=pi[k];
        if(s[k+1]==s[i])
            k++;
        pi[i]=k;

    }
}
int main()
{
    int k,nr=0;
    f>>s>>v;
    m=strlen(v);
    n=strlen(s)-1;
    prefix();
    k=-1;
    d[0]=k;
    for(int i=1;i<m;i++)
    {
        while(k>-1&&v[i]!=s[k+1])
            k=pi[k];
        if(v[i]==s[k+1])
            k++;
        d[i]=k;
    }
    for(int i=n;i<m;i++)
    {
        if(d[i]==n)
            nr++;
    }
    g<<nr<<endl;
    nr=0;
    for(int i=n;i<m;i++)
    {
        if(d[i]==n)
            {
                if(nr<=1000)
                {g<<i-n<<" ";
                nr++;
                }
                else
                    break;

            }
    }
    f.close();
    g.close();
    return 0;
}