Cod sursa(job #1419490)

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

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