재현이는 신문에서 어떤 문자열을 찾아 다른 곳에서 같은 문자열을 찾는 것에 집착한다.
그런데 재현이는 단순히 똑같은 문자열이 아니라, 신문에서 가장 길게 같은 문자열을 찾으려고 하루에 많은 시간을 투자한다.
그것을 옆에서 보며 불쌍히 여기던 정욱이는 주어진 문자열의 연속한 부분 문자열 중에서 문자열에 두 번 이상 등장하는 것들 중
가장 긴 것의 길이를 구하는 프로그램을 작성하여 재현이에게 선물로 주려고 한다.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 첫 번째 줄에 길이가 200,000 이하인 문자열이 주어진다.
이 문자열은 알파벳 소문자만으로 이루어져 있다.
출력
각 테스트 케이스마다 두 번 이상 등장하는 부분문자열 중에서 가장 길이가 긴 것의 길이를 출력한다.
만약 그런 부분 문자열이 없다면 0을 출력한다.
입력 예제
출력 예제
3 //TestCase 개수
sabcabcfabc //TestCase 1 입력
trutrutiktiktappop //TestCase 2 입력
abcdef //TestCase 3 입력
3 //TestCase 1 출력
4 //TestCase 2 출력
0 //TestCase 3 출력
첫번째 문자열에서는 “abc”가 부분 문자열로 세 번 나온다.
두번째 문자열에서는 “trut”혹은 “tikt”가 답이 된다.
세번째 문자열에는 두 번 이상 등장하는 부분 문자열이 없다.
#include <stdio.h>const int MAXN = 200005;int n;long long An, A[MAXN], t[MAXN];char S[MAXN];bool sort(int L, int R) { if (L == R) return 0; int M = (L + R) / 2; bool r1 = sort(L, M); bool r2 = sort(M + 1, R); if (r1 || r2) return 1; int l = L, r = M + 1, sz = L; while (l <= M && r <= R) { if (A[l] < A[r]) t[sz++] = A[l++]; else t[sz++] = A[r++]; } while (l <= M) t[sz++] = A[l++]; while (r <= R) t[sz++] = A[r++]; for (int i = L; i <= R; i++) { A[i] = t[i]; if (i > L && A[i] == A[i - 1]) return 1; } return 0;}bool ok(int L) { long long G = 1, hashvalue = 0; for (int i = 1; i < L; i++) G = G * 255LL; An = 0; for (int i = 1; i <= n; i++) { if (i > L) hashvalue -= G*(S[i - L] - 'a' + 1); hashvalue = hashvalue * 255LL + (S[i] - 'a' + 1); if (i >= L) A[An++] = hashvalue; } return sort(0, An - 1);}int main() { int T, tc; for (scanf("%d", &T), tc = 1; T--; tc++) { scanf("%s", S + 1); for (int i = 1; S[i]; i++) n = i; int lo = 0, hi = n - 1, md, res = 0; while (lo <= hi) { md = (lo + hi) / 2; if (ok(md)) { if (res < md) res = md; lo = md + 1; } else hi = md - 1; } printf("%d\n", res); }} |
#include <stdio.h>#define MAX 200000char A_s[MAX + 1];int A[MAX + 1];int N;long long h[MAX + 1];long long s[MAX + 1];int nowmax_val[MAX + 1];int nowmax_idx[MAX + 1];void makeHashTable(){ for (int a = 0; a < N; a++) { h[a] = 0; s[a] = 0; nowmax_val[a] = 0; } h[0] = A[0]; s[0] = A[0]; for (int a = 1; a < N; a++) { h[a] = h[a - 1] + (a + 1)*A[a]; s[a] = s[a - 1] + A[a]; }}long long Hash(int i, int j){ if (i == 0) return h[j]; long long ret = h[j] - h[i - 1] - (i)*(s[j] - s[i - 1]); if (ret < 0) { ret++; ret--; } return ret;}int HashSame(int i, int j, int lengh){ if (Hash(i, i + lengh - 1) == Hash(j, j + lengh - 1)) return 1; return 0;}int RealSame(int i, int j, int len){ for (int a = 0; a < len; a++) { if (A[i + a] == A[j + a]) continue; else return 0; } return 1;}int _MAX(int a, int b){ if (a > b) return a; return b;}#define MAXDUPL 100int temp[MAX + 1][MAXDUPL];int main(){ int T; //freopen("sample_input.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &T); while (T--) { scanf("%s", A_s); N = 0; while (A_s[N] >= 'a' && A_s[N] <= 'z') { A[N] = A_s[N] - 'a' + 1; N++; } int themax = 0; makeHashTable(); int low = 1; int high = N - 1; while (low < high) { int mid = (low + high) / 2; if (mid == low || mid == high) break; for (int i = 0; i < N; i++) temp[i][0] = 0; int found = 0; for (int i = 0; i + mid - 1 < N; i++) { int hhh = Hash(i, i+mid-1)%MAX; if (temp[hhh][0] >= 1) { int count = temp[hhh][0]; if (count >= MAXDUPL - 1) printf("duple "); for (int z = 1; z <= count; z++) { if (temp[hhh][z]!= i && RealSame(temp[hhh][z], i, mid)) { themax = _MAX(themax, mid); //themax = mid; low = mid; found = 1; break; } } if (found == 1) break; } temp[hhh][0]++; temp[hhh][temp[hhh][0]] = i; } if (found == 0) high = mid; } printf("%d\n", themax); } return 0;} |