Cod sursa(job #1419221)

Utilizator diana-t95FMI Tudoreanu Diana Elena diana-t95 Data 15 aprilie 2015 04:01:52
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#define maxn 2000007
int p[maxn], sol[1008], nsol;
string a, b;
void prefix()
{
    int n = a.size();
    int k = 0, i;
    p[0] = 0;
    for (i = 1; i < n; i++)
    {
        while( k && a[k] != a[i]) k = p[k];
        if (a[k] == a[i]) k++;
        p[i] = k;
    }
}
void kmp()
{
    int k, i;
    int n = a.size(), m = b.size();
    k = 0;
    for (i = 0; i < m; i++)
    {
        while (k && a[k]!=b[i]) k = p[k];
        if (a[k] == b[i]) k++;
        if (k == n && nsol < 1000) {sol[nsol++] = i - n + 1; k--;}
    }

}
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a>>b;
    prefix();
    kmp();
    g<<nsol<<'\n';
    for (int i = 0; i < nsol && i < 1000; i++)
        g<<sol[i]<<' ';
}