Cod sursa(job #407427)

Utilizator csizMocanu Calin csiz Data 2 martie 2010 12:33:06
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <string>
#include <vector>
#include <fstream>
using namespace std;

int main(){
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    string a,b;in>>a>>b;

    vector<int> gasiri(1000);
    int n=0;

    vector<int> prefix (a.length(),0);

    int k=-1;
    for(int i=1;i<a.length();i++){
        while(k>=0 and a[k+1]!=a[i]){
            k=prefix[k];
        }
        if(a[k+1]==a[i]){
            k++;
        }
        prefix[i]=k;
    }

    int q=-1;
    for(int i=0;i<b.length();i++){
        while(q>=0 and a[q+1]!=b[i]){
            q=prefix[q];
        }
        if(a[q+1]==b[i]){
            q++;
        }
        if(q+1==a.length()){
            if(n<1000){

                gasiri[n]=i-a.length()+1;

            }
            n++;
        }
    }
    out<<n<<endl;
    for(int i=0;i<n and i<1000;i++){
        out<<gasiri[i]<<" ";
    }
}