Cod sursa(job #580825)

Utilizator chibicitiberiuChibici Tiberiu chibicitiberiu Data 13 aprilie 2011 15:55:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

#define LIMIT 0x100000

char Text[LIMIT];
char Pattern[LIMIT];
int Prefix[LIMIT];
int LenT, LenP;

void PreProcess()
{
    Prefix[0] = -1;
    int pos = 2, cnd = 0;
    
    while (pos < LenP)
    {
      if (Pattern[pos-1] == Pattern[cnd])
      {
	cnd++; Prefix[pos] = cnd; pos++;
      }
      
      else if (cnd > 0) cnd = Prefix[cnd];
      else { Prefix[pos] = 0; pos++; }
    }
}

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

    fgets(Pattern, LIMIT, stdin);
    fgets(Text, LIMIT, stdin);
    
    LenT = strlen(Text); LenP = strlen(Pattern);

    PreProcess();

    int m = 0, i=0;
    queue<int> FoundMatches;

    while (m + i < LenT)
    {
        if (Pattern[i] == Text[m + i])
        {
            i++;
            if (i == LenP-1) {
                FoundMatches.push(m);
            }
        }
        else {
            m = m + i - Prefix[i];
            if (Prefix[i] > -1) i = Prefix[i];
            else i = 0;
        }
    }

    printf("%d\n", FoundMatches.size());

    for (int i=0; i<1000 && !FoundMatches.empty(); i++, FoundMatches.pop())
        printf("%d ", FoundMatches.front());

    return 0;
}