문자열 상용 알고리즘 요약
말 라 차 알고리즘 은 O (n) 시간 내 에 원본 문자열 을 찾 는 가장 긴 답장 서브 문자열 S 문 제 를 해결 하 는 알고리즘 입 니 다.소박 한 알고리즘 의 경우 모든 S [i] 에 대해 좌우 로 최대 답장 문자열 을 옮 겨 다 녀 야 하기 때문에 시간 복잡 도 는 O (n2) 입 니 다.
참고 블 로그:
https://www.cnblogs.com/czsharecode/p/9705358.html
https://www.cnblogs.com/yangxingsha/p/11722557.html(오류 가 있 습 니 다. "왼쪽 에서 오른쪽으로 배열 P [] 를 계산 합 니 다. Mi 는 이전에 가장 큰 답장 문자열 의 중심 위 치 를 얻 었 고 R 은 가장 큰 답장 문자열 이 도착 할 수 있 는 가장 오른쪽 끝 값 입 니 다.")
// S
string Manacher(string s){
//
string t = "$#";
for(int i=0; i p(t.size() , 0);
// mx( ),id(mx ),
//reCenter（ ）,reLen（ ）
int mx = 0, id = 0, reCenter = 0, reLen = 0;
// t
for(int i=1; i i ? min(mx - i , p[2*id - i]) : 1;
// i~mx ， mx ， ， p[i]++
while(t[i + p[i]] == t[i - p[i]]) p[i]++;
// t[i] mx mx id
if(i+p[i] > mx){
mx = i+p[i];
id = i;
}
//
if(p[i] > reLen){
reLen = p[i];
reCenter = i;
}
}
return s.substr((reCenter - reLen) / 2 , reLen - 1) ;
} 2. 문자열 해시
https://www.luogu.com.cn/problem/solution/P3370
https://www.luogu.com.cn/blog/yhzq/solution-p3370
3. 사전 트 리
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
