Cod sursa(job #1405412)

Utilizator maribMarilena Bescuca marib Data 29 martie 2015 10:40:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <cstring>
#define DIM 2000005

using namespace std;

int l, l1, k, poz;

char s[DIM], p[DIM];

int pi[DIM], v[1005];

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in.get(p+1, DIM);
    in.get();
    in.get(s+1, DIM);
    p[0]=' ';
    s[0]=' ';
    l=strlen(p)-1;
    pi[0]=0;
    k=0;
    for(int i=2; i<=l; ++i){
        while(k&&p[k+1]!=p[i])
            k=pi[k];
        if(p[k+1]==p[i])
            k++;
        pi[i]=k;
    }
    l1=strlen(s)-1;
    k=0;
    for(int i=1; i<=l1; ++i){
        while(k&&s[i]!=p[k+1])
            k=pi[k];
        if(s[i]==p[k+1])
            k++;
        if(k==l){
            poz++;
            if(poz<=1000)
                v[poz]=i;
            k=pi[k];
        }
    }
    out<<poz<<"\n";
    for(int i=1; i<=poz&&i<=1000; ++i){
        out<<v[i]-l<<" ";
    }
    in.close();
    out.close();
    return 0;
}