Cod sursa(job #1620101)

Utilizator Wh1plashOvidiu Taralesca Wh1plash Data 28 februarie 2016 20:37:20
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int p[2000001], m, n;
vector<int> sol;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
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;

    }
}
int main()
{

    cin>>x>>s;
    m=strlen(x); n=strlen(s);
    prefix(x);

    int k=0;
    for(int i=1;i<n;i++)
    {
        while(k>0 && x[k]!=s[i]) k=p[k-1];

        if(x[k]==s[i]) k++;
        if(k==m)sol.push_back(i-m+1);
    }
    cout<<sol.size()<<'\n';
    for(int i=0;i <min((int)sol.size(),1000);i++)
        cout<<sol[i]<<' ';
    return 0;
}