Cod sursa(job #1225523)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 2 septembrie 2014 19:06:12
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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] == 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++)
    {
        if(cand == -1)
            cand = 0;
        if(a[cand] == b[i])
            cand++;
        else
            cand = t[cand];
        if(cand == a.size())
        {
            raspuns++;
            if(raspuns <= 1000)
                sol[++sol[0]] = i - cand + 1;
            cand = t[cand-1];
        }
    }
    ki << raspuns << '\n';
    for(int i = 1; i <= sol[0]; i++)
        ki << sol[i] << " ";
}