Cod sursa(job #1475975)

Utilizator dimavascan94VascanDumitru dimavascan94 Data 24 august 2015 14:01:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
 
char a[2000005], b[2000005];
int occ[1005], f[2000005], nOcc = 0, i, j, sizeP, sizeS;
 
void buildF()
{
    f[0] = -1;
    f[1] = 0;
 
    //for (i = 2; i < sizeP; ++i)
    //{
    //  j = f[i - 1];
    //  while (j != -1 && a[i - 1] != a[j]) j = f[j];
    //  f[i] = j + 1;
    //}
 
    //same thing
    i = 2;
    j = 0;
    while (i < sizeP)
    {
        if  (a[i - 1] == a[j])  f[i++] = ++j;
        else if (j>0)    j = f[j];
        else    f[i++] = j = 0;
    }
}
 
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
 
    memset(a, 0, 2000005);
    memset(b, 0, 2000005);
 
    scanf("%s%s", a, b);
 
    sizeP = strlen(a);
    sizeS = strlen(b);
 
    buildF();//build the bad suffix good prefix function
 
    i = j = 0;
    while (i < sizeS)
    {
        if (b[i] == a[j])//the characters match
        {
            if (j == sizeP - 1)//found an occurence
            {
            	nOcc++;
                if (nOcc <= 1000)  occ[nOcc] = i-j; 
                j = f[j];
            }
            else i++,j++;
        }
        else//use the bad suffix to find good prefix
        {
            if (j == 0) i++;//no good prefix can exist, moving to the next char in string
            else    j = f[j];//trying to find good prefix for bad suffix        
        }
    }
 
    printf("%d\n", nOcc);
    for (i = 0; i < nOcc; ++i)   printf("%d ", occ[i]);
}