Cod sursa(job #1627694)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 3 martie 2016 18:24:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstring>
#include <fstream>

using namespace std;

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

#define N 2000001

char A[1 + N], B[1 + N];
int n, m;
int pred[N];
int rez[N], nr = 0;

inline void construiestePred()
{
    int i, k = 0;
    for(int i = 2; i <= n; i++)
    {
        while(k != 0 && A[i] != A[1 + k])
            k = pred[k];
        if(A[i] == A[1 + k])
            k++;
        pred[i] = k;
    }

    return;
}

inline void cautaInB()
{
    int i, k = 0;
    for(int i = 1; i <= m; i++)
    {
        while(k != 0 && B[i] != A[1 + k])
            k = pred[k];
        if(B[i] == A[1 + k])
            k++;
        if(k == n)
            rez[++nr] = i - n;
    }

    return;
}

inline void afiseaza()
{
    out << nr << '\n';

    if(nr > 1000)
        nr = 1000;
    for(int i = 1; i <= nr; i++)
        out << rez[i] << ' ';
}

int main()
{
    in >> (1 + A) >> (1 + B);
    n = strlen(1 + A);
    m = strlen(1 + B);
    construiestePred();
    cautaInB();
    afiseaza();
    return 0;
}