Light OJ: 1255 - Substring Frequency

substring_frequency.cpp

//region Template
#include <bits/stdc++.h>
//#define ONLINE_JUDGE
using namespace std;
//ios_base::sync_with_stdio(false);
inline int log(const char* format, ...)
{
#ifndef ONLINE_JUDGE
    va_list args;
    va_start(args, format);
    int code = vfprintf(stderr, format, args);
    va_end(args);
    return code;
#else
    return 0;
#endif
}

const double EPS    = 10e-8;
const int MAX       = 1000005;
const int INF       = 1 << 30;
//endregion
char A[MAX];
char B[2*MAX];
int Z[2*MAX];
int main(int argc, char **argv)
{
    int T;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        scanf("%s %s", A, B);
        int lb = strlen(B);
        strcat(B, A);
        int n = strlen(B);
        Z[0] = n;
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (r < i) {
                l = r = i;
                while (B[r-l] == B[r])
                    r++;
                Z[i] = r - l;
            } else {
                int b = r - i;
                int j = i - l;
                if (Z[j] < b) {
                    Z[i] = Z[j];
                } else if (Z[j] > b) {
                    Z[i] = b;
                } else {
                    l = i;
                    while (B[r-l] == B[r])
                        r++;
                    Z[i] = r - l;
                }
            }
        }

        int ans = 0;
        for (int i = lb; i < n; i++) {
            if (Z[i] >= lb)
                ans++;
        }

        printf("Case %d: %d\n", tc, ans);
    }
    return EXIT_SUCCESS;
}