Cod sursa(job #1225915)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 3 septembrie 2014 23:25:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
using namespace std;
ifstream ka("strmatch.in");
ofstream ki("strmatch.out");

const int A_MAX = 2000000;
string a, b;
int t[A_MAX + 1], raspuns, sol[1001];

void precompute()
{
    int cand = 0;
    t[0] = -1;
    t[1] = 0;
    for(int i = 2; i <= a.size(); i++)
    {
        while(cand >= 0)
        {
            if(a[i-1] == a[cand])
            {
                t[i] = ++cand;
                break;
            }
            else
                cand = t[cand];
        }
        if(cand == -1)
            cand = 0;
    }
}

int main()
{
    ka >> a >> b;
    precompute();
    int cand = 0;
    for(int i = 0; i < b.size(); i++)
    {
        while(cand && a[cand] != b[i])
            cand = t[cand];
        if(a[cand] == b[i])
            cand++;
        if(cand == a.size())
        {
            raspuns++;
            if(raspuns <= 1000)
                sol[++sol[0]] = i - cand + 1;
            cand = t[cand];
        }
    }
    ki << raspuns << '\n';
    for(int i = 1; i <= sol[0]; i++)
        ki << sol[i] << " ";
}