Cod sursa(job #1652208)

Utilizator BaweeLazar Vlad Bawee Data 14 martie 2016 19:28:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <string>

using namespace std;

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

string pattern , text;
int pre[2000005] , pos[1005] , n , m , num;

int main()
{
    f >> pattern >> text;

    n = pattern.size();
    m =    text.size();

    for(int i = n; i; --i) pattern[i] = pattern[i - 1]; pattern[0] = ' '; // indexez de la 1
    for(int i = m; i; --i) text[i] = text[i - 1]; text[0] = ' ';

    int k = 0;

    for(int i = 2; i <= n; ++i)
    {
        while(k && pattern[k + 1] != pattern[i])
            k = pre[k];
        if(pattern[k + 1] == pattern[i])
            ++k;
        pre[i] = k;
    }

    k = 0;

    for(int i = 1; i <= m; ++i)
    {
        while(k && pattern[k + 1] != text[i])
            k = pre[k];
        if(pattern[k + 1] == text[i])
            k++;
        if(k == n)
        {
            num++;
            k = pre[n];
            if(num <= 1000)
                pos[num] = i - n;
        }
    }

    g << num << "\n";
    for(int i = 1; i <= min(num , 1000); ++i)
        g << pos[i] << " ";

    return 0;
}