Cod sursa(job #282327)

Utilizator ScrazyRobert Szasz Scrazy Data 17 martie 2009 13:59:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <cstring>

const int maxl = 2000001;

const int d = 73; 
const int mod = 100007;

int n, m;
char a[maxl], b[maxl];
char match[maxl];

int t, p, h, d1, res;

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

    fgets(a, maxl, stdin);
    fgets(b, maxl, stdin);
    a[strlen(a) - 1] = '\0';
    b[strlen(b) - 1] = '\0';
    n = strlen(a); m = strlen(b);

    /*
    printf("%s\n", a);
    printf("%s\n", b);
    */
    d1 = 1;
    for (int i = 0; i < n; ++i)
    {
	p = (p * d + a[i]) % mod;
        t = (t * d + b[i]) % mod;	

	if (i != 0)
	    d1 = (d1 * d) % mod;
    } 

    if (p == t)
    { 
	int ok = 1;
	for (int j = 0; j < n; ++j)
	    if (a[j] != b[j])
	    {
		ok = 0;
		break;
	    }
	match[0] = ok;
	if (ok) ++res;
    }

    for (int i = n; i < m; ++i)
    {

	t = ((t - (b[i - n] * d1) % mod + mod) * d + b[i]) % mod;
	
	if (p == t)
	{ 
	    int ok = 1;
	    for (int j = 0; j < n; ++j)
		if (a[j] != b[i - n + j + 1])
		{
		    ok = 0;
		    break;
		}
	    match[i - n + 1] = ok;
	    if (ok) ++res;
	} 
    } 

    printf("%d\n", res);

    for (int i = 0; i < m; ++i)
	if (match[i]) printf("%d ", i);

    return 0;
}