HDU 3374 String Problem (최대 최소 표현법 템 플 릿 + KMP + next 배열 의 활용)
String Rank
SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7
and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once.
Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
Input Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters. OutputOutput four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also. Sample Input
abcder
aaaaaa
ababab
Sample Output 1 1 6 1
1 6 1 6
1 3 2 3
문제 풀이:
제목:
이 문 제 를 먼저 풀 고 가장 작은 표현법 이 무엇 인지 알 아야 한다.
이것 은 문자열 abcde 와 같은 예 를 들 어야 합 니 다.
그러면 이 문자열 의 동 구성 문자열 에서 사전 순서 가 가장 작은 것 을 구 하 는 것 은 바로 최소 표현 법 이 고 하나의 문자열 의 한 성질 입 니 다. 동 구성 문자열 은 매번 문자열 의 전체 순환 을 한 사람 씩 이동 시 켜 형 성 된 새로운 문자열 입 니 다.
예 를 들 어 방금 그 꼬치 의 동 구성 꼬치 는 bcdea, cdeab, deabc, eabcd 가 있 는데 그 중에서 가장 작은 꼬치 가 바로 최소 표현 법 입 니 다.
같은 이치 에서 최대 표현법 을 얻어 내다
이 문 제 는 최소 표현법 의 시작 위치 (1 부터) 와 수량, 최대 표현법 의 시작 위치 와 수량 을 구 할 수 있 도록 꼬치 를 주 는 것 이다.
생각:
최대 최소 표현법 은 템 플 릿 을 직접 세트 합 니 다. 수량 에 대해 서 는 문자열 이 순환 문자열 인지 아 닌 지 를 판단 합 니 다. 즉, 문자열 의 길 이 를 len 으로 설정 합 니 다. len% (len - next [len]) 는 0 이면 순환 문자열 입 니 다. 최대 최소 표현법 수량 은 len / (len - next [len] 입 니 다. 그렇지 않 으 면 순환 문자열 이 아니면 1 입 니 다.
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ACM - 계산 기하학 적 Pick - up sticks -- poj 2653Description Stan has n sticks of various length. The data for each case start with 1 <= n <= 100000, the number of stick...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.