Cod sursa(job #1744991)

Utilizator daymon_cDumitru Chitoraga daymon_c Data 20 august 2016 21:23:54
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 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 pos = 1;
    int cnd = 0;
 
    while (pos<m)
    {
        if(w[pos] == w[cnd])
            t[pos++] = ++cnd;
        else if(cnd>0)
            cnd = t[cnd];
        else
            pos++;
    }
}
 
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
 
    fgets(w, sizeof(w), stdin);
    fgets(s, sizeof(s), stdin);
 
    n = strlen(s) - 1;
    m = strlen(w) - 1;
 
    table();

    //i for s, p for w
    for(int i=0, p=0; i + p <= n;)
    {
        if(s[i+p] == w[p])
        {
            p++;
            if(p == m)
            {
                sl++;
                if(sl<=1000)
                    sol[sl] = i;
                p = t[p]; 
                i += p | 1;
            }
        }
        else
        {
            p = t[p];
            i += p | 1;
        }
         
    }
 
    printf("%d\n", sl);
    for (int i = 1; i <= minim(sl, 1000); i++)
    {
        printf("%d ", sol[i]);
    }
 
    return 0;
}