Cod sursa(job #2254898)

Utilizator Victor_InczeVictor Incze Victor_Incze Data 6 octombrie 2018 09:58:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define LMAX 2000005

using namespace std;

ifstream in ("strmatch.in");
ofstream out ("strmatch.out");

int lcs[LMAX], s[LMAX];
int n, m;
char a[LMAX], b[LMAX];

void calc_lcs()
{
    int len=0;
    for (int i=1; i<n; i++)
    {
        if (a[i]==a[len])
            len++;
        else
        {
            len=0;
            if (a[i]==a[len])
                len++;
        }
        lcs[i]=len;
    }
}

void solve()
{
    int k=0;
    for (int i=0; i<m; i++)
    {
        while (k!=0 && a[k]!=b[i])
            k=lcs[max(0,k-1)];
        if (a[k]==b[i])
            k++;
        if (k==n)
        {
            s[0]++;
            s[s[0]]=i-n+1;
            k=lcs[k-1];
        }
    }
}

int main()
{
    in >> a >> b;
    n=strlen(a);
    m=strlen(b);
    calc_lcs();
    solve();
    out << s[0] << '\n';
    for (int i=1; i<=(min(s[0],1000)); i++)
        out << s[i] << " ";
    return 0;
}