Cod sursa(job #2416924)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 28 aprilie 2019 16:40:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

#define Nmax 2000000

using namespace std;

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

int N, M;

string A, B;

int Prefix[Nmax + 5];
int Answer[Nmax + 5];

int ans = 0;

static inline void generateMyPrefixes ();

int main()
{
    fin >> A >> B;
    generateMyPrefixes ();
    int index = -1;
    for (int i = 0; i < M; ++i)
    {
        while (0 <= index && A[index + 1] != B[i])
            index = Prefix[index];
        if (A[index + 1] == B[i])
            ++index;
        if (index == N - 1)
            Answer[++ans] = i - N + 1;
    }
    fout << ans << "\n";
    ans = min (ans, 1000);
    for (int i = 1; i <= ans; ++i)
        fout << Answer[i] << " ";
    return 0;
}

static inline void generateMyPrefixes ()
{
    N = A.size ();
    M = B.size ();
    Prefix[0] = -1;
    int index = -1;
    for (int i = 1; i < N; ++i)
    {
        while (0 <= index && A[i] != A[index + 1])
            index = Prefix[index];
        if (A[i] == A[index + 1])
            ++index;
        Prefix[i] = index;
    }
}