Cod sursa(job #1898424)

Utilizator mihaizsZsisku mihaizs Data 2 martie 2017 00:28:38
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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("grader_test21.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 );



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

        if(w[cnt]==w[p-1]){
            cnt++;
            t[p]=t[p-1]+1;
            p++;
        }
        else if(cnt>0){
            cnt  = t[cnt];
        }
        else{
            t[p]=0;
            p++;
        }

    }
    vector<int> sols;
    int i=0;
    p=0;
    while(p+i <= n){
        if(i==m){
            nrsol++;
            sols.push_back(p);
            //if(nrsol == 1000)
                //goto Done;
            p=p+i-t[i];
            i=t[i];
        }
        if(s[p+i]==w[i])
        {
            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;
}