Cod sursa(job #1303223)

Utilizator EpictetStamatin Cristian Epictet Data 27 decembrie 2014 19:25:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int N, M, k, nr, V[2000010], Sol[2000010];
string A, B;

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

int main()
{
    fin >> A >> B;
    N = A.size(); M = B.size();
    Prefix();
    for (int i = 0; i < M; i++)
    {
        while (k && A[k] != B[i]) k = V[k-1];
        if (A[k] == B[i]) k++;
        if (k == N)
        {
            k = V[k-1];
            if (++nr <= 1000) Sol[nr] = i - N + 1;
        }
    }
    fout << nr << '\n';
    for (int i = 1; i <= 1000 && i <= nr; i++) fout << Sol[i] << ' ';
    fout.close();
    return 0;
}