Cod sursa(job #1955171)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 5 aprilie 2017 20:34:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

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

char a[2000005], b[2000005];
int n, m, i, q, lg[2000005], sol[1005], ns;

int main() {
    f.getline(a+1, sizeof(a));
    f.getline(b+1, sizeof(b));
    n = strlen(a+1), m = strlen(b+1);
    for (i = 2; i <= n; i++) {
        while (a[q+1] != a[i] && q)
            q = lg[q];
        if (a[q+1] == a[i]) q++;
        lg[i] = q;
    } q = 0;
    for (i = 1; i <= m; i++) {
        while (a[q+1] != b[i] && q)
            q = lg[q];
        if (a[q+1] == b[i]) q++;
        if (q == n) {
            ns++;
            if (ns<= 1000) sol[ns] = i-q;
            q = lg[q];
        }
    }
    g << ns << '\n';
    ns= min(ns,1000);
    for (i =1; i <= ns; i++) g << sol[i] << ' ';
    return 0;
}