Cod sursa(job #1628809)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 4 martie 2016 10:47:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define nmax 2000005

using namespace std;

int n, m, rez[nmax];
char P[nmax], S[nmax];

int prefix[nmax];

void preprocessPattern()
{
    int a = 0;
    prefix[1] = 0;
    for (int i = 2; i <= m; i++)
    {
        while (a > 0 && P[a + 1] != P[i])
        {
            a = prefix[a];
        }
        if (P[a + 1] == P[i])
            a++;
        
        prefix[i] = a;
        
    }
}

void kmp()
{
    
    int a = 0;
    
    for (int i = 1; i <= n; i++)
    {
        while (a > 0 && P[a + 1] != S[i]) a = prefix[a];
        if (P[a + 1] == S[i]) a++;
        if (a == m)
        {
            rez[ ++rez[0] ] = i - m;
            a = prefix[a];
        }
    }
    
    
}

int main()
{
    
    ifstream fi("strmatch.in");
    ofstream fo("strmatch.out");
    
    fi >> (P+1);
    fi >> (S+1);
    
    m = int(strlen(P + 1));
    n = int(strlen(S + 1));
    
    preprocessPattern();
    
    kmp();
    
    fo << rez[0] << "\n";
    for (int i = 1; i <= min(1000, rez[0]); i++)
        fo << rez[i] << " ";
    
    fi.close();
    fo.close();
    
    return 0;
}