Cod sursa(job #1631981)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 5 martie 2016 20:38:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

char s[4000100];
int z[4000100];
int sol[1100];

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    gets(s + 1);
    int m = strlen(s + 1);
    int n = m;
    int res = 0;
    s[++n] = '$';
    gets(s + n + 1);
    n = strlen(s + 1);

    int l = 0, r = 0;
    for (int i = 2; i <= n; ++i) {
        if (i >= r) {
            while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])
                ++z[i];
            l = i;
            r = i + z[i] - 1;
        } else {
            int i2 = i - l + 1;
            z[i] = z[i2];
            if (i + z[i] - 1 >= r) {
                z[i] = r - i + 1;
                while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])
                    ++z[i];
                l = i;
                r = i + z[i] - 1;
            }
        }
        if (z[i] == m) {
            ++res;
            if (res <= 1000)
                sol[res] = i - m - 2;
        }
    }

    printf("%d\n", res);
    for (int i = 1; i <= min(res, 1000); ++i)
        printf("%d ", sol[i]);
    return 0;
}