Cod sursa(job #2053621)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 31 octombrie 2017 22:57:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005], B[2000005];
int N, M;
int P[2000005];
int Sol[1005];
void Read()
{
    f.getline(A + 1, 2000005);
    f.getline(B + 1, 2000005);
    N = strlen(A + 1);
    M = strlen(B + 1);
}

void pref()
{
    int k = 0;
    for(int i = 2; i <= N; i++)
    {
        while(k > 0 && A[i] != A[k + 1])
            k = P[k];
        if(A[i] == A[k + 1])
            ++k;
        P[i] = k;
    }
}

void Solve()
{
    int k = 0, cnt = 0;
    for(int i = 1; i <= M; i++)
    {
        while(k > 0 && B[i] != A[k + 1])
        {
            k = P[k];
        }
        if(B[i] == A[k + 1])
            k++;
        if(k == N)
        {
            ++cnt;
            if(cnt <= 1000)
                Sol[cnt] = i - N + 1;
        }
    }
    g << cnt << "\n";
    for(int i = 1; i <= min(cnt, 1000); i++)
        g << Sol[i] - 1 << " ";
    g << "\n";
}
int main()
{
    Read();
    pref();
    Solve();
    return 0;
}