Cod sursa(job #2109412)

Utilizator PushkinPetolea Cosmin Pushkin Data 19 ianuarie 2018 18:16:01
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define pb push_back
vector<int> prfx(string s)
{
    int n=s.size(), k=0, i;
    vector<int> v{0};
    for(i=1;i<n;i++)
    {
        while(k>0&&s[k]!=s[i])k=v[k-1];
        if(s[k]==s[i])k++;
        v.pb(k);
    }
    return v;
}
vector<int> v;
vector<int> KMP(string s, string sb)
{
    int n=sb.size(), m=s.size(), q=-1, i;
    vector<int> res;
    v=prfx(sb);
    for(i=0;i<m;i++)
    {
        while(q>0&&sb[q+1]!=s[i])
            q=v[q];
        if(sb[q+1]==s[i])q++;
        if(q==n-1)res.pb(i-n+1);
    }
    return res;
}
string A, B;
vector<int> res;
int main()
{
    getline(f, B);
    getline(f, A);
    res=KMP(A, B);
    g<<res.size()<<'\n';
    for(auto a:res)g<<a<<' ';
    f.close();
    g.close();
    return 0;
}