Cod sursa(job #1816320)

Utilizator victorpapa98Papa Victor-Alexandru victorpapa98 Data 26 noiembrie 2016 12:49:21
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
# include <cstdio>
# include <cstring>
# include <vector>
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 = 0;

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

        if (s[i] == pattern[k+1])
        {
            k++;
            if (k == strlen(pattern) - 1)
            {
                total ++;
                sol.push_back(i-k);
            }
        }
    }

    printf("%d\n", total);
    for (int i : sol)
        printf("%d ", i);
}

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

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