Cod sursa(job #1628262)

Utilizator maribMarilena Bescuca marib Data 3 martie 2016 22:21:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
#define DMAX 2000005

using namespace std;

char p[DMAX], s[DMAX];

int poz[DMAX], v[1002];

int lungs, lungp, k, ans;

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