Cod sursa(job #1513064)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 28 octombrie 2015 22:31:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <string.h>

#define NMax 2000010

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int strl, patl, prefsuf[NMax], sol[1010], k;
char str[NMax], pattern[NMax];

void find_prefsuf()
{
    int j=0;
    prefsuf[1] = 0;
    
    for (int i = 2; i <= patl; i++) {
        while (j > 0 && pattern[i] != pattern[j+1])
            j = prefsuf[j];
        
        if (pattern[i] == pattern[j+1])
            j++;
        prefsuf[i] = j;
    }
}

int main()
{
    f>>(pattern+1)>>(str+1);
    strl = strlen(str+1);
    patl = strlen(pattern+1);
    
    find_prefsuf();
    
    int j=0;
    for (int i=1; i <= strl && k < 1000; i++) {
        while (j > 0 && pattern[j+1] != str[i])
            j = prefsuf[j];
        
        if (pattern[j+1] == str[i])
            j++;
        
        if (j == patl)
            sol[++k] = i - j;
            
    }
    
    g << k << "\n";
    for (int i=1; i<=k; i++)
        g << sol[i] << " ";
    
    return 0;
}