Cod sursa(job #1225903)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 3 septembrie 2014 22:57:10
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#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;
    int i = 2;
    while(i < a.size())
    {
        if(a[i-1] == a[cand])
        {
            cand++;
            t[i] = cand;
            i++;
        }
        else if(cand > 0)
            cand = t[cand];
        else
        {
            t[cand] = 0;
            i++;
        }
    }
}

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