Cod sursa(job #1096800)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 2 februarie 2014 16:48:48
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<string>
using namespace std;
int i,n,pref[2000005],sol[1005],nr;
string s1,s2;

void makeprefix(){
     n=s1.length()-1;
     pref[1]=0; pref[0]=-1;
     for (int i=2; i<=n; ++i) {
         int aux=pref[i-1];
         while (s1[i]!=s1[aux+1]&&aux>=0) aux=pref[aux]; 
         pref[i]=aux+1;
         }
}

int main(void) {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    getline(fin,s1); s1=' '+s1;
     getline(fin,s2); s2=' '+s2;
    makeprefix();
     
    int poz=1;
    
    for (i=1; i<s2.length(); ++i) {
        
        while (s2[i]!=s1[poz]&&poz>0) poz=pref[poz];
        if (s2[i]==s1[poz]) ++poz;
        if (poz==n+1) {
                    ++nr; poz=pref[n]+1;
                    if (nr<=1000) sol[nr]=i-1;
                    }
        }
        
      fout<<nr<<"\n";
     for (i=1; i<=min(1000,nr); ++i) fout<<sol[i]-n+1<<" ";
  return(0);
}