[백준 BOJ] C++) 1605번: 반복 부분 문자열

문제

• 링크

1605번: 반복 부분문자열

예제 이해

• 예제) tellmetellmetetetetetetetellme 의 부분문자열의 길이가 11이라고 한다
• 길이 11의 부분문자열을 찾는데 애를 먹었다
• 찾은 부분 문자열은 etetetetete 이다. 그 이유는?

풀이 접근 방식

• 길이 L의 부분 문자열을 찾는다.
• 부분 문자열을 찾고 없으면 길이 L-1의 부분 문자열을 찾는다.

소스 코드 (1차 시도)

#include <iostream>
#include <string>

using namespace std;

int solution(int L, string input) {		
	string subString;
	int subStringLen = L-1;
	if (L == 1) return 0;
	while (subStringLen >= 1) {
		for (int i = 0; i < L; i++) {
			subString = input.substr(i, subStringLen);
			if (input.substr(i+1).find(subString) != std::string::npos) return subStringLen;
			if ((L - i) == subStringLen) break;	
		}
		subStringLen--;
	}
	return 0;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int L;
	string input;
	cin >> L;
	cin >> input;
	cout << solution(L,	input) << endl;
}

채점 결과

• 시간 초과

시간 초과 원인

• O(M * N)

소스 코드 (참고)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
char str[200005];
const int p = 29;
const int MOD = 10007;
int Len; 
int pexp[200005];
vector<int> hashTable[10007];		//시작 index를 갖는다.

int main() {
    pre();
    cin >> Len;
    solve();
}

void pre() {
    pexp[0] = 1;
    for (int i = 1; i <= 200000; i++) {
	    pexp[i] = pexp[i - 1] * p % MOD;
    }
}

void solve() {
    scanf("%s", str);
    int l = 0, r = Len;
    while (l < r) {
	    int m = (l + r + 1) / 2;
	    if (ok(m)) l = m;
	    else r = m - 1;
    }
    cout << l << endl;
}

bool ok(int L){
	init();		//길이 L의 중복 부분문자열이 존재하는지를 리턴
    int hash = 0;
    for (int i = 0; i < L; i++) {
	    hash *= p;
	    hash += str[i] - 'a';
	    hash %= MOD;
    }
    hashTable[hash].push_back(0);
    for (int i = L; i < Len; i++) {
		hash -= (str[i - L] - 'a') * pexp[L - 1] % MOD;
		hash = (hash + MOD) % MOD;
		hash *= p; hash += str[i] - 'a';
    	hash %= MOD;
    	if (hashTable[hash].size()) {
    		for (int idx : hashTable[hash]) {
    			if (real_match(idx, i - L + 1, L)) return true;
    		}
    	}
    	hashTable[hash].push_back(i-L+1);
    }
    return false;
}
    
void init() {
    for (int i = 0; i < MOD; i++) {
	    hashTable[i].clear();
    }
}

bool real_match(int s1, int s2, int L) {
	for (int i = 0; i < L; i++) {
		if (str[s1 + i] != str[s2 + i]) { 
        	return false; 
        } 
    } return true; 
}

// 출처: https://eine.tistory.com/entry/백준저지-1605번-반복-부분문자열-문제-풀이 [아인스트라세의 소프트웨어 블로그]