Cod sursa(job #1899170)

Utilizator mihaizsZsisku mihaizs Data 2 martie 2017 16:08:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include<string>
#include<string.h>
#include<vector>
#include<fstream>

#define cin f
#define cout g
/**/
using namespace std;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    string s, w;
    cin>>w>>s;

    int m=w.size();
    int n=s.size();
    int nrsol=0;
    int *t= new int[m+3];
    memset(t, 0, sizeof(int) *m );

   // cerr<<"m"<<m<<"\n";

    t[0]=-1;
    t[1]=0;
    int cnt=0, p=2;
    while(p<m){

        if(w[cnt]==w[p-1]){
            cnt++;
            t[p]=cnt;
            p++;
        }
        else if(cnt>0){
            cnt  = t[cnt];
        }
        else{
            t[p]=0;
            p++;
        }
    }
/*
    for(int i=0; i<=m; i++)
        cerr<<t[i]<<" ";
    cerr<<"\n";
    */
    vector<int> sols;
    int i=0;
    p=0;
    while(p+i < n){

        if(s[p+i]==w[i])
        {

              if(i==m-1){
                nrsol++;
                sols.push_back(p);
                p=p+i-t[i];
                i=t[i];
            }
            else i++;
        }

        else if(i==0){
            p++;
        }
        else{
            p=p+i-t[i];
            i=t[i];

        }

    }
    cout<<sols.size()<<"\n";
    for(int i=0; i<min(nrsol, 1000); i++)
        cout<<sols[i]<<" ";


    return 0;
}