Cod sursa(job #1818118)

Utilizator KusikaPasa Corneliu Kusika Data 28 noiembrie 2016 20:38:34
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;

int f[2000001];
int n, m, p=2, k, p1, p2, nr;
int sol[1001];
char a[2000001], b[2000001];

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    cin >> a >> b;
    n = strlen(a), m = strlen(b);

    f[0] = -1, f[1] = 0;
    while (p < n)
        if (a[p-1] == a[k]) f[p++] = ++k;
        else
            if (k>0) k = f[k];
            else f[p++] = 0;

    while (p1 + p2 < m)
        if (a[p2] == b[p1 + p2])
            if (p2 == n - 1) {
                if (++nr <= 1000) sol[nr-1] = p1;
                if (f[p2] > -1) p1 += p2 - f[p2], p2 = f[p2];
                else p2 = 0, p1++;
            }
            else p2++;
        else
            if (f[p2] > -1) p1 += p2 - f[p2], p2 = f[p2];
            else p2 = 0, p1++;

    cout << nr << " ";
    for (int i = 0; i < min(1000,nr); i++) cout << sol[i] << " ";
}