Cod sursa(job #259960)

Utilizator catalina5catalina serban catalina5 Data 16 februarie 2009 10:34:06
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<iostream>
#include<fstream>

using namespace std;

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

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

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

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