Cod sursa(job #1420677)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 18 aprilie 2015 20:23:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
char A[2000005], B[2000005], s[4000005];
int n, m, i, flc, sol[1005], z[4000005], mln;
void Zalg()
{
    int l, r;
    l = r = 1;
    for(i = 2; i <= n; i++)
    {
        if(r >= i)
            z[i] = min(z[i - l + 1], r - i + 1);
        for(; i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]; z[i]++);
        if(z[i] >= m && i > m)
        {
            flc++;
            if(flc <= 1000)
                sol[flc] = i - m - 1;
        }
        if(i + z[i] - 1 > r)
        {
            l = i;
            r = i + z[i] - 1;
        }
    }
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", (A + 1), (B + 1));
    n = strlen(A + 1);
    m = strlen(B + 1);
    strncpy(s + 1, A + 1, n);
    strncpy(s + n + 1, B + 1, m);
    mln = n;
    n += m;
    m = mln;
    Zalg();
    printf("%d\n", flc);
    flc = min(1000, flc);
    for(i = 1; i <= flc; i++)
        printf("%d ", sol[i]);
    return 0;
}