Cod sursa(job #1338296)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 9 februarie 2015 22:22:20
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[2000001], y[2000001];
int l[2000001], k, m, n, nra, poz[1001];
void read()
{
    f >> x + 1;
    f >> y + 1;
    x[0] = ' ';
    y[0] = ' ';
}
void contstruct()
{
    n = strlen(x) - 1;
    m = strlen(y) - 1;
    l[1] = 0;
    k = 0;
    for(int i = 2; i<=n; i++)
    {
        while(k > 0 && x[i] != x[k + 1])
            k = l[k];
            if(x[i] == x[k + 1]) k++;
            l[i] = k;
    }
}
void solve()
{
    k = 0;
    for(int i = 1; i<=m; i++)
    {
        while(k > 0 && y[i] != x[k + 1])
            k = l[k];
        if(y[i] == x[k + 1]) k++;
        if(k == n)
        {
            nra ++;
            if(nra <= 100)
                poz[nra] = i - n;
        }
    }
    g << nra << '\n';
}
int main()
{
    read();
    contstruct();
    solve();
    if(nra <= 1000)
    for(int i = 1; i<= nra; i++)
    g << poz[i] << ' ';
    else for(int i = 1; i<=1000; i++)
        g << poz[i] << ' ';
    return 0;
}