Cod sursa(job #1498982)

Utilizator EpictetStamatin Cristian Epictet Data 9 octombrie 2015 23:11:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int n, m, V[2000010], S[1010];
char A[2000010], B[2000010];

void Read()
{
    fin.get(A, 2000005, '\n');
    n = strlen(A);
    fin.get();
    fin.get(B, 2000005, '\n');
    m = strlen(B);
    fin.close();
}

void Prefix()
{
    for (int i = 1, k = 0; i < n; i++)
    {
        if (k && A[i] != A[k]) k = V[k - 1];
        if (A[i] == A[k]) k++;
        V[i] = k;
    }
}

void Solve()
{
    Prefix();
    for (int i = 0, k = 0; i < m; i++)
    {
        while (k && B[i] != A[k]) k = V[k - 1];
        if (B[i] == A[k]) k++;
        if (k == n)
        {
            k = V[k - 1];
            S[0] ++;
            if (S[0] <= 1000) S[S[0]] = i - n + 1;
        }
    }
}

void Write()
{
    fout << S[0] << '\n';
    S[0] = min(S[0], 1000);
    for (int i = 1; i <= S[0]; i++) fout << S[i] << ' ';
    fout << '\n';
    fout.close();
}

int main()
{
    Read();
    Solve();
    Write();

    return 0;
}