Cod sursa(job #1243247)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 15 octombrie 2014 18:32:25
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#define n_max_value 200005
#include <cstring>
#include <queue>
#define o_constraint 1000

#include <algorithm>

using namespace std;

char a[n_max_value],b[n_max_value];
queue <int> qu;
int t[n_max_value],no;
int n,m;
void next(){

  t[1]=0;
  int k=0;
  for(int q=2 ;q<=m;q++){
     while(k&&a[k+1]!=a[q])k=t[k];
     if(a[k+1]==a[q])
        k++;
     t[q]=k;
  }
}

void solve(){

    next();
    int q=0;

    for(int i=1;i<=n;i++){
        while(q&&a[q+1]!=b[i])
            q=t[q];
        if(a[q+1]==b[i])
            q++;
        if(q==m){
            no++;
            if(no<=o_constraint)
               qu.push(i-m+1);
            q=t[q];
        }
    }
}

void print(){
    freopen("strmatch.out","w",stdout);
    printf("%d\n",no);
    while(!qu.empty()){
        printf("%d ",qu.front());
        qu.pop();
    }

}


int main(void){
    freopen("strmatch.in", "r" ,stdin);
    fgets(a,sizeof(a),stdin);
    fgets(b,sizeof(b),stdin);
    n=strlen(b);m=strlen(a);
    solve();
    print();
}