Cod sursa(job #758457)

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

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