Cod sursa(job #1496111)

Utilizator sabauandrei98Sabau Andrei sabauandrei98 Data 4 octombrie 2015 13:34:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;

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

#define mm 2000005
int v[mm];
char rad[mm],sur[mm];
int sol[1001];

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

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

    v[1] = 0;
    for(int i = 2; i <= rad_size; i++)
    {
        int j = v[i-1];

        while(j and rad[i] != rad[j+1])
            j = v[j];

        if (rad[i] == rad[j+1])
                v[i] = j+1;
            else
                v[i] = 0;
    }
    int p = 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)
            {
                if (p < 1000)
                    {
                        p++;
                        sol[p] = i - rad_size;
                    }
                else
                    p++;
            }
    }

    g<<p<<'\n';
    for(int i = 1; i <= min(p,1000); i++)
        g<<sol[i]<<" ";

    return 0;
}