Cod sursa(job #1168573)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 8 aprilie 2014 23:50:42
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<fstream>
#include<string>
using namespace std;
string text, pattern;
int esec[2000005], i, nrsol, sol[1005];

void makeprefix(){
     
     esec[0]=-1;
     for (int i=2; i<pattern.length(); ++i) {
         int k=i-1;
         while (k>0 && pattern[esec[k]+1]!=pattern[i]) k=esec[k];
         esec[i]=esec[k]+1;
         }
         
}

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