문자열 처리 새로운 사고 네요. [볼 수 밖 에 없 음]

원문 보기:
http://www.ibaiyang.org/2012/03/25/repeat-substring/
최근 에 을 보고 많은 사람들 이 이 신 서 를 봐 야 한다 고 말 했다. 그래서 나 도 한 권 샀 다. 그러나 이 책 을 받 았 을 때 도 보통 이 라 고 생각 했다. 앞의 몇 장의 예 제 는 매우 평범 하고 작가 가 분석 한 것 이 자신 이 실 용적 이지 않다 고 느 꼈 다. 예 를 들 어 2 분 검색 에서 2, 3 장 을 말 했다. 비록 작가 가 2 개의 검색 에 대한 이해 와 실현 이지 만트집 을 잡 았 지만 전체적으로 재 미 없 었 고 사람 에 게 탁 트 이 는 느낌 을 주지 않 았 다. 2 장 을 보 았 을 때 변위 어의 알고리즘 을 말 해서 사람 을 매 료 시 켰 다. 그래서 나 는 미 친 듯 이 계속 보 았 다. 오늘 은 반복 문자열 의 실현 방식 을 보 았 다. 나 는 기 쁘 게 바로 박문 을 보 내 서 그것 이 얼마나 기묘 한 지 증명 하고 싶 었 다.
문자열 의 가장 긴 중복 문자열 을 구 하 는 것 은 긴 문자열 에서 중복 되 는 문자열 을 찾 는 것 입 니 다. 그리고 그 길이 가 가장 깁 니 다. 저 는 이 문제 의 파생 의미 도 매우 크다 고 생각 합 니 다. 특히 현재 검색엔진 시대 에.예 를 들 어 바나나 의 가장 긴 문자열 은 ana 이 고, tian xian 의 가장 긴 문자열 은 ian 이다.자, 어떻게 이 루어 졌 는 지 봅 시다.

int cmp_str(char* p, char* q)
{
	int size = 0;
	while(p && q && *p == *q){
		size++;
		p++;
		q++;
	}
	return size;
}

int maxlen = -1;
int current_size = -1;
for(int i = 0; i < n; i++){
	for(int j = i + 1; j < n; j++){
                if( (current_size = cmp_str(&input_string[i], &input_string[j]) ) > maxlen ){
			maxlen    = current_size;
			low_index = i;
			high_index = j;
		}
	}
}

그 중에서 가장 큰 문자열 길 이 는 원래 문자열 의 i 에서 j 의 위치 에 존재 합 니 다. 물론 이것 은 누구나 생각 할 수 있 는 2B 알고리즘 입 니 다. 저도 열 에 포함 되 어 있 습 니 다. 아, 계속 노력 하 세 요.
그렇다면 저 자 는 이 문 제 를 어떻게 생각 할 까. 그 중 에 '접미사 배열' 을 사용 했다. 아주 오래 전부터 한 ACM 대원 이 접미사 배열 을 통과 한 다 는 말 을 들 었 지만 그 가 무슨 말 을 했 는 지 캐 묻 지도 않 았 다. 오늘 공교롭게도 또 만 나 원 수 는 길이 좁 았 다.
접미사 배열 이 무엇 입 니까? 사실은 매우 간단 합 니 다. 저 는 이것 이 프로그램의 예비 처리 부분 에 속 하고 간단 한 데이터 구조 라 고 생각 합 니 다.
이 구 조 는 워드 라 고 가정 하 는 문자 포인터 배열 입 니 다.문 자 를 읽 을 때, 우 리 는 모든 요소 가 입력 문자열 에 해당 하 는 문 자 를 가리 키 도록 워드 를 초기 화 합 니 다

int i = 0;
	char ch;
	while( (ch = cin.get()) != '
' ){
		input_string[i] = ch;
		word[i++]       = &input_string[i];
		max_word++;
	}

	input_string[i] = '\0';
	word[i]         = NULL;

예 를 들 어 우리 가 입력 한 문자열 이 baiyang 이 라면

word[0] = "baiyang";
word[1] = "aiyang";
word[2] = "iyang";
word[3] = "yang";
word[4] = "ang";
word[5] = "ng";
word[6] = "g";

이것 은 '접미사 배열' 이 됩 니 다. 이 진 트 리 를 이해 할 수 있다 면 이것 도 이해 할 수 있 을 거 라 고 믿 습 니 다.
긴 문자열 이 배열 에 두 번 나타 나 면 두 개의 서로 다른 접미사 에 나타 날 것 입 니 다. 따라서 우리 팀 은 같은 접 두 사 를 찾기 위해 정렬 합 니 다.
바나나 접미사 배열 정렬

word[0] = "a";
word[1] = "ana";
word[2] = "anana";
word[3] = "banana";
word[4] = "na";
word[5] = "nana";

그래서 ana 가 가장 길 고 각각 1, 2 개의 접미사 배열 에 존재 하 는 것 을 보 았 다.우리 가 접미사 배열 에 순 서 를 매 긴 후에 우 리 는 배열 을 옮 겨 다 닐 수 있다.

 int i = 0;
	int index   = -1;
	int max_len = -1;

	int current_size = 0;
	for(i = 0; i < max_word - 1; i++) { 		if( (current_size = cmp_str(word[i], word[i+1])) > max_len ) {
			max_len = current_size;
			index   = i;
		}
	}

이렇게 가장 긴 하위 문자열 의 길 이 는 max 입 니 다.len 입 니 다. 출발점 은 index 위치 입 니 다.그래서 알고리즘 의 복잡 도 는 이전의 n 제곱 에서 nlog (n) 로 떨 어 졌 다.하지만 그 중의 접미사 배열 구 조 는 우리 가 생각해 볼 만하 다 고 생각한다.
전송: http://www.ibaiyang.org/2012/03/25/repeat-substring/  정품 지원
 
질 좋 은 글 을 만 드 는 데 더 많은 관심 을 기울 여 술 로 은혜 를 갚 는 다
고 품질의 문장 을 만 들 기 위해 서 는  추천 하 다.  한번 해 보 자...감사합니다. 제 후속 글 을 지 켜 봐 주세요. 더 멋 있 을 거 예요.
sina 웨 이 보 에 주목 하 세 요: http://weibo.com/baiyang26
술 로 은혜 를 갚 는 공식 블 로그: http://www.ibaiyang.org [구 글 리더 로 구독 추천!]
술 을 은혜 와 원한 을 없 애 는 공식 콩잎: http://www.douban.com/people/baiyang26/
본 블 로 그 를 옮 기 고 싶 으 시 면 출처 를 밝 혀 주 십시오.
본문 에 의견 이나 건의 가 있 으 시 면 메 시 지 를 남 겨 주세요.