Cod sursa(job #1744972)

Utilizator daymon_cDumitru Chitoraga daymon_c Data 20 august 2016 19:59:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 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;

    //i for s, p for w
    for(int i=0, p=0; i + p<n || sl >= 1000;)
    {
        if(s[i+p] == w[p])
        {
            if(p == m - 1)
            {
                sol[sl++] = i;
                p = t[p]; 
                i += maxim(p, 1);
            }
            else p++;
        }
        else
        {
            p = t[p];
            i += maxim(p, 1);
        }
        
    }

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

    return 0;
}