Cod sursa(job #1408217)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 29 martie 2015 22:09:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector<int> sol;
int p[2000001],m,n;
char s[2000001],x[2000001];
void prefix(char s[])
{
    int k=0;
    for(int i=1;i<m;i++)
    {
        while(k>0 && s[k]!=s[i])k=p[k-1];
        if(s[k]==s[i])k++;
        p[i]=k;
    }
}
void kmp(char s[],char x[])
{
    prefix(x);
    int k=0;
    for(int i=0;i<n;i++)
    {
        while(k>0 && x[k]!=s[i])k=p[k-1];
        if(x[k]==s[i])k++;
        if(k==m)sol.pb(i-m+1);
    }
}

int main()
{
    in>>x;m=strlen(x);
    in>>s;n=strlen(s);
    kmp(s,x);
    out<<sol.size()<<'\n';
    for(int i=0;i<min((int)sol.size(),1000);i++)out<<sol[i]<<' ';
    return 0;
}