Spoj NAJPF – CPP solution

Problem: http://www.spoj.com/problems/NAJPF/

Here are 3 solutions:
– Morris-Pratt (0.04)
– Morris-Pratt automation (0.06 dew to size of alphabet)
– Hashing (0.10 due to false matches)

#include <cstdio>
#include <iostream>
using namespace std;

char T[1000001], P[1000001];
int fail[1000001];
int ans[1000001];
int ansSz;

int main() {
    int t;
    int sz = int('Z')-int('A')+1;
    scanf("%d",&t);
    while (t--) {
        ansSz=0;
        scanf("%s%s", T, P);

        fail[0] = 0;
        fail[1] = 0;
        int l = 2;
        int j = 0;
        while (P[l-1]) {
            if (P[l-1] != P[j]) {
                if (j == 0) {
                    fail[l++] = 0;
                }
                j = fail[j];
            } else {
                while(P[l-1] == P[j]) {
                    fail[l++] = ++j;
                }
            }
        }
        j=0;
        int i = 0;
        while(T[i]) {
            if (T[i] == P[j]) {
                i++;
                j++;
                if (j == l-1) {
                    ans[ansSz++] = i-l+2;
                }
            } else {
                if (j == 0) i++;
                j = fail[j];
            }

        }
        if (ansSz==0) {
            printf("Not Found");
        } else {
            printf("%dn", ansSz);
            for (int i = 0; i < ansSz; i++) printf("%d ", ans[i]);
        }
        printf("n");

    }
    return 0;
}
#include <iostream>
using namespace std;

char T[1000001], P[1000001];
int automata[1000001][30];
int ans[1000001];
int ansSz;

int main() {
    int t;
    int sz = int('Z')-int('A')+1;
    scanf("%d",&t);
    while (t--) {
        ansSz=0;
        scanf("%s%s", T, P);

        int l = 1;
        int link=0;
        for (int i = 0; i < sz; i++) automata[0][i] = 0;
        automata[0][P[0]-'a'] = 1;
        while(P[l]) {
            for (int i = 0; i < sz; i++) {
                automata[l][i] = automata[link][i];
            }
            automata[l][P[l]-'a'] = l+1;
            link = automata[link][P[l]-'a'];
            l++;
        }
        for (int i = 0; i < sz; i++) {
            automata[l][i] = automata[link][i];
        }
        int i = 0;
        int c = 0;
        while(T[i]) {
            if (c==l) {
                ans[ansSz++] = i-l+1;
            }
            c = automata[T[i]-'a'];
            i++;
        }
        if (c==l) {
            ans[ansSz++] = i-l+1;
        }
        if (ansSz==0) {
            printf("Not Found");
        } else {
            printf("%dn", ansSz);
            for (int i = 0; i < ansSz; i++) printf("%d ", ans[i]);
        }
        printf("n");

    }
    return 0;
}
#include <cstdio>
#include <iostream>
using namespace std;

#define MAX 1000009
char T[MAX], P[MAX];
int ans[MAX];
int ansSz;
#define MOD 1000000007LL
#define Z 33LL
long long dp[MAX];

inline long long mod(long long num) {
    if (num < 0LL) num += MOD;
    num %= MOD;
    return num;
}

inline bool ok(int s) {
    int k=0;
    while(P[k] && T[s+k] && P[k] == T[s+k]) k++;
    return !P[k];
}

int main() {
    int t;
    int sz = int('Z')-int('A')+1;
    dp[0] = 1LL;
    for (int i = 1; i< MAX; i++) dp[i] = mod(dp[i-1]*Z);
    scanf("%d",&t);
    while (t--) {
        ansSz=0;
        scanf("%s%s", T,P);
        int l = 0;
        long long h = 0LL;
        long long h2 = 0LL;
        while (P[l] && T[l]) {
            h = mod(h*Z + (P[l]-'a')*1LL);
            h2 = mod(h2*Z + (T[l]-'a')*1LL);
            l++;
        }
        int i = l;
        while(T[i]) {
            if (h == h2 && ok(i-l)) {
                ans[ansSz++] = i-l+1;
            }
            h2 = mod(mod((h2 - dp[l-1]*1LL*(T[i-l]-'a'))*Z) + (T[i]-'a')*1LL);
            i++;
        }
        if (h == h2 && ok(i-l)) {
            ans[ansSz++] = i-l+1;
        }

        if (ansSz==0) {
            printf("Not Found");
        } else {
            printf("%dn", ansSz);
            for (int i = 0; i < ansSz; i++) {
                printf("%d ", ans[i]);
            }
        }
        printf("n");

    }
    return 0;
}

I have 3 implementations since I got quite many segmentation fauls (didn’t read the input size properly) and quite many wrong answers.

Leave a Reply

Your email address will not be published. Required fields are marked *