Cod sursa(job #1495984)

Utilizator sabauandrei98Sabau Andrei sabauandrei98 Data 4 octombrie 2015 00:57:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

#define mm 2000005
int v[mm];
string rad,sur;
vector<int> q;

int main()
{
    f >> rad >> sur;
    int rad_size = rad.size();
    int sur_size = sur.size();

    for(int i = rad_size; i > 0; i--)   rad[i] = rad[i-1];
    for(int i = sur_size; i > 0; i--)   sur[i] = sur[i-1];

    v[1] = 0;
    for(int i = 2, j = 0; i <= rad_size; i++)
    {
        while(j and rad[i] != rad[j+1])
            j = v[j];

        if (rad[i] == rad[j+1])
                j++;

        v[i] = j;
    }
    int cn = 0;
    for(int i = 1, j = 0; i <= sur_size; i++)
    {
        while(j and sur[i] != rad[j+1])
            j = v[j];

        if (sur[i] == rad[j+1])
                j++;

        if (j == rad_size)
            {
                j = v[j];
                if (cn <= 1000)
                {
                    q.push_back(i - rad_size);
                    cn = q.size();
                }
            }
    }

    g<<q.size()<<'\n';
    for(int i = 0; i < min(1000,cn); i++)
        g<<q[i]<<" ";

    return 0;
}