Cod sursa(job #1965194)

Utilizator andrei232000Andrei Maria andrei232000 Data 14 aprilie 2017 00:19:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int l, L, i, j, contor;
int p[2000005], start[2000005];
char c[2000005], sir[2000005];
int main()
{
    fin>>c;
    fin>>sir;
    l = strlen(c);
    L = strlen(sir);
    for(i = 1; i < l; ++i)
    {
        while(j && c[i] != c[j])
        {
            j = p[j - 1];
        }
        if(c[i] == c[j])
        {
            ++j;
            p[i] = j;
        }
        else if(!j)
        {
            p[i] = j;
        }
    }
    j = 0;
    i = 0;
    while(i < L)
    {
        while(c[j] != sir[i] && j)
        {
            j = p[j - 1];
        }
        if(c[j] == sir[i])
        {
            ++j;
            ++i;
            if(j == l)
            {
                j = p[l - 1];
                start[contor] = i - l;
                ++contor;
            }
        }
        else if(!j)
        {
            ++i;
        }
    }
    fout<<contor<<'\n';
    for(i = 0; i < contor; ++i)
    {
        fout<<start[i]<<" ";
    }
    return 0;
}