Cod sursa(job #1091748)

Utilizator pulseOvidiu Giorgi pulse Data 25 ianuarie 2014 23:05:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define NMAX 2000010

int n, m, num;
int table[NMAX];
char w[NMAX], s[NMAX];
queue <int> sol;

void ReadData ()
{
    scanf ("%s \n %s", w, s);
    n = strlen (s);
    m = strlen (w);
    w[m] = '#';
}

void Init_Table ()
{
    table[0] = -1;
    int i = 2, k = 0;
    while (i <= m)
	 if (w[i - 1] == w[k])
    {
    	++k;
    	table[i] = k;
      ++i;
    }
    else if (k)
		k = table[k];
    else
    {
    	table[i] = 0;
    	++i;
     }
}

void KMP ()
{
	 int k = 0;
    for (int i = 0; k + i < n; )
    {
        if (s[k + i] == w[i])
        {
            if (i == m - 1)
            {
                ++num;
                if (num <= 1000)
                    sol.push(k);
            }
            ++i;
        }
        else
        {
            k += i - table[i];
            i = (table[i] > -1) ? table[i] : 0;
        }
    }
}

int main ()
{
    freopen ("strmatch.in", "r", stdin);
    freopen ("strmatch.out", "w", stdout);
    ReadData();
    if (m > n) {printf ("0"); return 0;}
    Init_Table();
    KMP ();
    printf ("%d\n", num);
    while (!sol.empty())
    {
        printf ("%d ", sol.front());
        sol.pop();
    }
    return 0;
}