Cod sursa(job #758461)

Utilizator memaxMaxim Smith memax Data 15 iunie 2012 19:00:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <string>
#include <fstream>
#include <queue>
using namespace std;

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