Cod sursa(job #1793890)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 31 octombrie 2016 17:25:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int  N = 2000010, M = 1010;

int n, k, i, j, z[2 * N], lena, lenb, p, sol[M];
char a[N], b[N], s[2 * N];

int main() {
    fin >> a >> b;
    lena = strlen(a) - 1;
    lenb = strlen(b) - 1;
    strcpy(s, "0");
    strcat(s, a);
    strcat(s, "#");
    strcat(s, b);
    n = strlen(s) - 1;
    k = 1;
    for (i = 2; i <= n; ++i) {
        if (k + z[k] - 1 < i) {
            p = i;
            for (j = 1; p <= n && s[p] == s[j]; ++p, ++j);
            z[i] = p - i;
            k = i;
        } else {
            z[i] = min(z[i - k + 1], k + z[k] - i);
            for (; z[i] + i <= n && s[z[i] + i] == s[z[i] + 1]; ++z[i]);
            if (i + z[i] - 1 > k + z[k] - 1) {
                k = i;
            }
        }
    }
    k = 0;
    for (i = lena + 2; i <= n; ++i) {
        if (z[i] > lena) {
            k++;
            if(k <= 1000)
                sol[k] = i - lena - 3;
        }
    }
    fout << k << "\n";
    k = min(1000, k);
    for (i = 1; i <= k; ++i) {
        fout << sol[i] << " ";
    }
    return 0;
}