Cod sursa(job #1792634)

Utilizator mariakKapros Maria mariak Data 30 octombrie 2016 16:28:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define Dim 2000010
#define Lim 1000
FILE *fin  = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

using namespace std;
char pattern[Dim], text[Dim];
int F[Dim], lp, lt;
vector <int> sol;

void internal_rules()
{
    F[1] = 0;
    int j = 0;
    for (int i = 2; i <= lp; ++ i)
    {
        while (pattern[i] != pattern[j + 1] && j)
            j = F[j];
        if(pattern[i] == pattern[j + 1])
            ++ j;
        F[i] = j;
    }
}

void KMP()
{
    int i, j = 0;
    internal_rules();

    for (i = 1; i <= lt; ++ i)
    {
        while (text[i] != pattern[j + 1] && j)
            j = F[j];

        if (text[i] == pattern[j + 1])
            ++ j;
        if (j == lp && sol.size() < Lim)
            sol.push_back(i - lp);
    }
}
void write()
{
    printf("%d\n", sol.size());
    for(int i = 0; i < sol.size(); ++ i)
        printf("%d ", sol[i]);
}
int main()
{
    gets(pattern + 1);
    lp = strlen(pattern + 1);
    gets(text + 1);
    lt = strlen(text + 1);
    KMP();
    write();
    return 0;
}