Skip to content

Instantly share code, notes, and snippets.

@rendon
Created June 4, 2014 03:24
Show Gist options
  • Save rendon/43bbc8f3fbcb8d231c99 to your computer and use it in GitHub Desktop.
Save rendon/43bbc8f3fbcb8d231c99 to your computer and use it in GitHub Desktop.
Light OJ: 1255 - Substring Frequency
//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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment