Cod sursa(job #2173982)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 16 martie 2018 10:08:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005], B[2000005];
int P[2000005], N, M;
vector <int> Sol;
void pref()
{
    int q = 0;
    P[1] = 0;
    for(int i = 2; i <= N; i++)
    {
        while(q && A[i] != A[q + 1])
            q = P[q];
        if(A[i] == A[q + 1])
            q++;
        P[i] = q;
    }
}
void Solve()
{
    int q = 0, nb = 0;
    for(int i = 1; i <= M; i++)
    {
        while(q && B[i] != A[q + 1])
            q = P[q];
        if(B[i] == A[q + 1])
            q++;
        if(q == N)
        {
            nb++;
            if(nb <= 1000)
            Sol.push_back(i - N);
        }
    }
    g << nb << "\n";
    for(int i = 0; i < Sol.size(); i++)
    {
        g << Sol[i] << " ";
    }
    g << "\n";
}
int main()
{
    f.getline(A + 1, 2000005);
    f.getline(B + 1, 2000005);
    N = strlen(A + 1);
    M = strlen(B + 1);
    pref();
    Solve();
    return 0;
}