Cod sursa(job #106442)

Utilizator tm_raduToma Radu tm_radu Data 18 noiembrie 2007 17:13:17
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.35 kb
#include <stdio.h>
#include <string.h>
using namespace std;

char t[10000000];
char c[21], d;
int p[21];
int i, j;
int sol;
int n, m;
char b[50001][21];
int k = 0;

void Prefix(char s[]);

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    scanf("%s", t);
    scanf("%c", &d);
    scanf("%s", &c);

    while ( c[0] != '#' )
    {
        Prefix(c);
        n = strlen(t);
        m = strlen(c);
        int ok = 1;
        for ( j = 1; j < k; j++ )
            if ( strcmp(b[j], c) == 0 ) ok = 0;
        if ( ok ) 
        {
            k++,
            strcpy(b[k], c);
            Prefix(c);
            j = 0;
            for (i = 0; i < n; i++)
            {
                while ( j > 0 && c[j] != t[i] )
                    j = p[j];
                if ( c[j] == t[i] ) j++;
                if (j == m)
                {
                    sol++;
                    break;
                }
            }
        }    
        
        c[0] = '#';
        scanf("%c", &d);
        scanf("%s", c);
    }
    printf("%d\n", sol);
    return 0;
}

void Prefix(char s[])
{
	int i, k, n;
	p[1] = 0; k = 0; n = strlen(s);
	for (i = 1; i < n; i++)
	{
  		while ( k > 0 && s[k] != s[i] )
  			k =  p[k];

  		if ( s[k] == s[i] ) k++;

  		p[i+1] = k;
  	}
}