Cod sursa(job #1004588)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 3 octombrie 2013 10:37:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

vector < int > sol;
char a[2000007], b[2000007];
int n, m, x;
int p[2000007];

void fa_x (char b[], int i)
{
    while(x > 0 && a[x + 1] != b[i])
        x = p[x];
    if(a[x + 1] == b[i])
            ++ x;
}

void make_prefix()
{
    for(int i = 2; i <= m; ++ i)
    {
        fa_x(a, i);
        p[i] = x;
    }
}

int main()
{
    int nr2 = 0  ;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(a + 1);
    gets(b + 1);
    m = strlen(a + 1);
    n = strlen(b + 1);
    make_prefix();
    x = 0;
    int ok = 0;
    for(int i = 1; i <= n; ++ i)
    {
        fa_x(b, i);
        if(x == m)
        {
            x = p[m];
            sol.push_back(i - m);
            if(sol.size() > 1000)
                sol.erase(sol.begin(), sol.begin() + 1);
        }
    }
    int nr = 1000;
    printf("%d\n", (int)sol.size()) ;
    for(int i = 0; i < min(nr, (int)sol.size()); ++ i)
        printf("%d ", sol[i]);
    return 0 ;
}