Cod sursa(job #1143856)

Utilizator smaraldaSmaranda Dinu smaralda Data 16 martie 2014 10:43:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 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;

inline void expandPattern (int start, int i) {
    right = i;
    do {
        ++ right;
        }while(pattern[right] == pattern[right - start + 1] && right <= n);
    -- right;
}

inline void expandTxt (int start, int i) {
    right = i;
    do {
        ++right;
        }while(txt[right] == pattern[right - start + 1] && right <=m );
    -- right;
}

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

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

    right = 1;
    for(i = 2; i <= n; ++ i) {
        if(pattern[i] != pattern[1]) {
            z[i] = 0;
            continue;
        }

        if(i > right || z[i - pos + 1] + i - 1 >= right) {
            pos = i;
            expandPattern(pos, i);
            z[i] = right - i + 1;
        } else
            z[i] = z[i - pos + 1];
    }

    right = 0;
    for(i = 1 ; i <= m; ++ i) {
        if(txt[i] != pattern[1]) {
            p[i] = 0;
            continue;
        }
        if(i > right || z[i - pos + 1] + i - 1 >= right) {
            pos = i;
            expandTxt(pos, i);
            p[i] = right - i + 1;
        } else
            p[i] = z[i - pos + 1];

        if(p[i] == n && sol.size() < 1000)
            sol.push_back(i);
    }

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