Cod sursa(job #1502929)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 15 octombrie 2015 11:18:56
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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 (a[k+1]!=a[i] && k>=0) 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();
    
    int nrapp=0;
    k=1;
    
    for (i=1; i<b.length(); ++i) {
        
        while (b[i]!=a[k] && k>0) k=pref[k];
        
        ++k;
        
        if (k==a.length()) {
                             k=pref[a.length()-1]+1;
                             ++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;
}