Cod sursa(job #1816390)

Utilizator victorpapa98Papa Victor-Alexandru victorpapa98 Data 26 noiembrie 2016 13:52:28
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
# include <cstdio>
# include <cstring>
# include <vector>
# include <algorithm>
using namespace std;

FILE *f = freopen("strmatch.in", "r", stdin);
FILE *g = freopen("strmatch.out", "w", stdout);

const int L_MAX = 2000010;

char pattern[L_MAX];
char s[L_MAX];

int last[L_MAX];

int total;
vector <int> sol;

void compute_prefix()
{
    int k = -1;
    last[0] = -1;

    for (int i=1; i<strlen(pattern); i++)
    {
        while (pattern[i] != pattern[k+1] && k != -1)
            k = last[k];

        if (pattern[i] == pattern[k+1])
        {
            last[i] = k+1;
            k++;
        }
        else
            last[i] = -1;
    }

    /*for (int i=0; i<strlen(pattern); i++)
        printf("%d ", last[i]);*/
}

void solve()
{
    int k = -1;
    int l_pattern = strlen(pattern);
    int l_s = strlen(s);

    for (int i=0; i<l_s; i++)
    {
        while (s[i] != pattern[k+1] && k != -1)
            k = last[k];

        if (s[i] == pattern[k+1])
        {
            k++;
            if (k == l_pattern - 1)
            {
                total ++;

                if (total <= 1000)
                    sol.push_back(i-k);

                k = last[k];
            }
        }
    }

    printf("%d\n", total);

    for (int i=0; i<min(total, 1000); i++)
            printf("%d ", sol[i]);
}

void read()
{
    scanf("%s\n%s", pattern, s);
}

int main()
{
    read();
    compute_prefix();
    solve();
    return 0;
}