Cod sursa(job #758458)

Utilizator memaxMaxim Smith memax Data 15 iunie 2012 18:57:31
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <string>
#include <fstream>
#include <queue>
using namespace std;

int main(){
    ifstream cinr ("strmatch.in");
    ofstream cour ("strmatch.out");
    
    string b;
    cinr >> b;
    char a;
    
    queue<int> q;
    int m=b.size();
    int p[m+1],j,t=0,tr=0;
    p[0]=0; p[m]=0;
    
    for(int i=1; i<m; i++){
            j=p[i-1];
            while(j>0 && b[j]!=b[i]){ j=p[j-1]; }
            if(b[j]==b[i]){ j++; }
            p[i]=j; 
            }
    j=0;
    
    while(cinr.good()){
            cinr >> a;           
            while(j>0 && b[j]!=a){ j=p[j-1]; }
            if(b[j]==a){ j++; }
            if(j==m){
                     if(q.size()<1000){ q.push(tr-m+1); }
                     t++;
                     }
            tr++;
            }
    
    cour << t << "\n";
    while(!q.empty()){
                      cour << q.front() << " ";
                      q.pop();
                      }
                      
    cinr.close();
    cour.close();
    return(0);
    }