Cod sursa(job #1674745)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 4 aprilie 2016 20:36:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

const int dmax = 2000001;

char A[1 + dmax], B[1 + dmax];

int pref[dmax];

int r[dmax];
int nr;

int N, M;

void prefix()
{
    int k = 0, i;

    for(i = 2; i <= M; i++)
    {
        while(k != 0 && A[1 + k] != A[i]) k = pref[k];

        if(A[i] == A[1 + k]) k++;

        pref[i] = k;
    }
}

void solve()
{
    int k = 0, i;

    for(i = 1; i <= N; i++)
    {
        while(k !=0 && A[k + 1] != B[i]) k = pref[k];

        if(B[i] == A[1 + k]) k++;

        if(k == M) r[++nr] = i - M;
    }
}

void write()
{
    int i;

    out << nr << '\n';

    if(nr > 1000) nr = 1000;

    for(i = 1; i <= nr; i++) out << r[i] << " ";
}

int main()
{
    in.getline(1 + A, dmax);
    in.getline(1 + B, dmax);

    M = strlen(1 + A);
    N = strlen(1 + B);

    prefix();
    solve();
    write();

    return 0;
}