Cod sursa(job #1143874)

Utilizator smaraldaSmaranda Dinu smaralda Data 16 martie 2014 11:02:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;

const int NMAX = 2e6;
char pattern[NMAX + 5], txt[NMAX + 5];
int right, p[NMAX + 5], z[NMAX + 5], n, m;
vector <int> sol;

int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int pos, i, cnt;

    gets(pattern); n = strlen(pattern);
    gets(txt); m = strlen(txt);

    right = 0;
    for(i = 1; i < n; ++ i)
        if(i > right) {
            pos = right = i;
            while(right < n && pattern[right - pos] == pattern[right])
                ++ right;
            z[i] = right - pos;
            -- right;
        } else {
            if(z[i - pos] + i <= right)
                z[i] = z[i - pos];
            else {
                pos = i;
                while(right < n && pattern[right - pos] == pattern[right])
                    ++ right;
                z[i] = right - pos;
                -- right;
            }
        }

    cnt = 0;
    right = -1;
    for(i = 0 ; i < m; ++ i) {
        if(i > right) {
            pos = right = i;
            while(right < m && pattern[right - pos] == txt[right])
                ++ right;
            p[i] = right - pos;
            -- right;
        } else {
            if(z[i - pos] + i <= right)
                p[i] = z[i - pos];
            else {
                pos = i;
                while(right < m && pattern[right - pos] == txt[right])
                    ++ right;
                p[i] = right - pos;
                -- right;
            }
        }

        if(p[i] == n)
            sol.push_back(i);
    }

    printf("%d\n",sol.size());
    for(i = 0; i < sol.size() && i <= 999; ++ i)
        printf("%d ",sol[i]);
    return 0;
}