Cod sursa(job #1502947)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 15 octombrie 2015 11:59:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<string>
#include<vector>
using namespace std;

string a,b;
int i,j,pref[2000005],k;
vector<int> sol;

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

int main(void) {
    
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    
    getline(cin,a);
    getline(cin,b);
    
    a=' '+a;
    b=' '+b;
    
    make_prefix();
    
    /*for (i=1; i<a.length(); ++i) {
       
       cout<<pref[i]<<" ";
        
    }
    return 0;  */
    
    int nrapp=0;
    k=0;
    
    for (i=1; i<b.length(); ++i) {
        
        while (k>0 && b[i]!=a[k+1]) k=pref[k];
        
        if (b[i]==a[k+1]) ++k;
        
        if (k==a.length()-1) {
                             k=pref[k];
                             ++nrapp;
                             if (nrapp<=1000) sol.push_back(i-a.length()+1);
                             }
        
        }
    
    cout<<nrapp<<"\n";
    
    for (i=0; i<sol.size(); ++i) cout<<sol[i]<<" ";
    
    return 0;
}