Cod sursa(job #1689866)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 14 aprilie 2016 16:53:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define INF numeric_limits<int>::max()
#define int64 long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector<int> sol;
int pi[2000001];
void prefix(string x)
{
    int k=0;
    for(int i=1;i<(int)x.size();i++)
    {
        while(x[i]!=x[k] && k>0)
            k=pi[k-1];
        if(x[i]==x[k])
            k++;
        pi[i]=k;
    }
}
void kmp(string x,string s)
{
    prefix(x);
    int k=0;
    for(int i=0;i<(int)s.size();i++)
    {
        while(s[i]!=x[k] && k>0)
            k=pi[k-1];
        if(s[i]==x[k])
            k++;
        if(k==(int)x.size())
            sol.pb(i-x.size()+1);
    }
}
int main()
{
    in>>a>>b;
    kmp(a,b);
    out<<sol.size()<<'\n';
    for(int i=0;i<min((int)sol.size(),1000);i++)
        out<<sol[i]<<' ';
    return 0;
}