Cod sursa(job #1518527)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 5 noiembrie 2015 22:29:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000000 + 2;

char A[MAX_N], B[MAX_N];
int pi[MAX_N];

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

    in >> (A + 1) >> (B + 1);

    int N = strlen(A + 1);
    int M = strlen(B + 1);

    int k = 0;
    pi[1] = 0;

    for (int i = 2; i <= N; ++i)
    {
        while (k > 0 && A[i] != A[k + 1])
            k = pi[k];

        if (A[i] == A[k + 1])
            k++;

        pi[i] = k;
    }

    vector<int> solutions;

    k = 0;

    for (int i = 1; i <= M; ++i)
    {
        while (k > 0 && B[i] != A[k + 1])
            k = pi[k];

        if (B[i] == A[k + 1])
            k++;

        if (k == N)
        {
            solutions.push_back(i - N);
            k = pi[k];
        }
    }

    out << solutions.size() << "\n";

    for (int i = 0; i < min(1000, (int)solutions.size()); ++i)
        out << solutions[i] << ' ';

    in.close();
    out.close();

    return 0;
}