Cod sursa(job #2349590)

Utilizator BaraianTudorBaraian Tudor Stefan BaraianTudor Data 20 februarie 2019 16:28:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int l=2000005;
char c[l],d[l];
int lps[l],n,m,cont,v[2005];
void lp()
{
    int i=1,inc=0;
    while(i<n)
    {
        if(c[i]==c[inc])
        {
            inc++;
            lps[i++]=inc;
        }
        else
        {
            if(inc==0)++i;
            else
                inc=lps[inc-1];
        }
    }
}
void sol()
{
    int i=0,inc=0;
    while(i<m)
    {
        if(d[i]==c[inc])
        {
            ++inc;
            ++i;
            if(inc==n)
            {
                if(cont<1005)
                v[++cont]=i-n;
                inc=lps[inc-1];
            }
        }
        else
        {
            if(inc==0)
            {
                i++;
            }
            else
            {
                inc=lps[inc-1];
            }
        }
    }
}
int main()
{
    in.getline(c,l);
    in.getline(d,l);
    n=strlen(c),m=strlen(d);
    lp();
    sol();
    out<<cont<<'\n';
    cont=min(1000,cont);
    for(int i=1;i<=cont;i++)
    {
        out<<v[i]<<' ';
    }
    return 0;
}