Cod sursa(job #1744992)

Utilizator daymon_cDumitru Chitoraga daymon_c Data 20 august 2016 21:24:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <string.h>
#define minim(a, b) ((a < b) ? a : b)
#define maxim(a, b) ((a > b) ? a : b)
#define NMax 2000005

int t[NMax];
char s[NMax], w[NMax];
int n, m, sol[1024], sl;

//t[x] = how much w needs to pad left to continue the checl
void table()
{
    int k=0;
    for(int i=2; i<=m; ++i)
    {
        while(k && w[k+1] != w[i])
            k = t[k];
        if(w[k+1] == w[i]) k++;
        t[i] = k;
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    fgets(w+1, sizeof(w), stdin);
    fgets(s+1, sizeof(s), stdin);

    n = strlen(s+1);
    m = strlen(w+1);
    if(w[m] == '\n') m--;
    if(s[n] == '\n') n--;

    table();
    
    //i for s, p for w
    int k=0;
    for(int i=1; i<=n; ++i)
    {
        while(k && w[k+1] != s[i])
            k=t[k];
        if(w[k+1] == s[i])
            k++;
        if(k==m)
        {
            k=t[k];
            sl++;
            if(sl<=1000) sol[sl] = i-m;
        }
    }

    printf("%d\n", sl);
    for (int i = 1; i <= minim(sl, 1000); i++)
    {
        printf("%d ", sol[i]);
    }

    return 0;
}