Cod sursa(job #2039585)

Utilizator HumikoPostu Alexandru Humiko Data 14 octombrie 2017 17:57:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

vector <int> v;

int pi[4000005];
char s[4000005];

void kmp (int n, int l)
{
    int poz = 0;
    for ( int i = 2; i <= n; ++i )
    {
        pi[i] = pi[i-1];
        while (pi[i] && s[i] != s[pi[i]+1])
            pi[i] = pi[pi[i]];
        if ( s[i] == s[pi[i]+1] )
            pi[i]++;
        if (pi[i] == l)
        {
            ++poz;
            if ( poz <= 1000 )
                v.push_back(i-l-l-1);
        }
    }
    fout << poz << '\n';
    for ( auto x:v )
        fout << x << " ";
}

int main()
{
    int n, l;
    fin>>(s+1);
    n = strlen (s+1);
    l = n;
    s[n+1] = '$';
    fin>>(s+n+2);
    n = strlen (s+1);
    kmp (n, l);
}