Cod sursa(job #218584)

Utilizator catalina5catalina serban catalina5 Data 2 noiembrie 2008 18:08:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<iostream>
#include<fstream>

using namespace std;

int n,m,poz[1001],rez[200001],nr;
char a1[200001],a2[200001];

ifstream fin("strmath.in");
ofstream fout("strmath.out");

void prefix(){
    int k=0;
    poz[0]=0;
    for(int i=2;i<=m;i++){
        while(k&&a2[k]!=a2[i+1])
            k=poz[k];
        if(a2[k+1]==a2[i])
            k++;
        poz[i]=k;
    }
}

void numarare(){
     int k=0;
     for (int i=1;i<=n;i++){
          while(k&&a2[k+1]!=a1[i])
               k=poz[k];
          if(a2[k+1]==a1[i])
               k++;
          if (k==m){
               nr++;
               if(nr<=1000)
                    rez[nr]=i-m;
               k=poz[k];
          }
     }
}

void afisare(){
    fout<<nr<<"\n";
    if(nr>1000)
        nr=1000;
    for(int i=1;i<=nr;i++)
        fout<<rez[i]<<" ";
    fout<<"\n";
}

int main(){
    fin>>a1>>a2;
    n=strlen(a1)-1;
    m=strlen(a2)-1;
    prefix();
    numarare();
    afisare();
    fin.close();
    fout.close();
    return 0;
}