Cod sursa(job #2175846)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 16 martie 2018 19:34:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int l[2000010], a[200010];
char s[200010], p[200010];

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int i, j, n, m, x=0;
    fin.getline(p, 2000010);
    fin.getline(s, 2000010);
    n=strlen(s);
    m=strlen(p);
    i=1;
    l[0]=0;
    j=0;
    while(i<m)
    {
        if (p[i]==p[j])
        {
            l[i]=j+1;
            i++,j++;
        }
        else
            if (j==0)
                l[i++]=0;
            else
                j=l[j-1];
    }
    i=j=0;
    while (i<n)
    {
        if (s[i]==p[j])
        {
            i++,j++;
            if (j==m)
            {
                a[x++]=i-j;
                j=l[j-1];
            }
        }
        else
            if (j==0)
                i++;
            else
                j=l[j-1];
    }
    fout << x << "\n";
    for (i=0; i<x; i++)
        fout << a[i] << " ";
    return 0;
}