Cod sursa(job #1423919)

Utilizator UAIC_HreapcaVlasNegrusUAIC Hreapca Vlas Negrus UAIC_HreapcaVlasNegrus Data 22 aprilie 2015 23:42:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

char S[2000010], T[2000010];
int i, k, N, M, prefix[2000010], sol;
vector<int> solution;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf(" %s",(S+1));
    scanf(" %s",(T+1));
    N = strlen((S+1));
    M = strlen((T+1));
    for(i = 2; i <= N; i++)
    {
        while(k && S[k + 1] != S[i])
            k = prefix[k];
        if(S[k + 1] == S[i])
            k = k + 1;
        prefix[i] = k;
    }
    for(i = 1, k = 0; i <= M; i++)
    {
        while(k && S[k + 1] != T[i])
            k = prefix[k];
        if(S[k + 1] == T[i])
            k = k + 1;
        if(k == N)
        {
            if(sol < 1000)
                solution.push_back(i - N);
            sol = sol + 1;
            k = prefix[k];
        }
    }
    printf("%d\n",sol);
    for(vector<int>::iterator it = solution.begin(); it != solution.end(); it++)
        printf("%d ", *it);
    return 0;
}