문자열 s가 있다고 가정하고 s의 동종 부분 문자열의 수를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9+7을 반환합니다. 문자열의 모든 문자가 같을 때 문자열은 동질적이라고 합니다.
따라서 입력이 s ="xyyzzzxx"와 같으면 동종 하위 문자열이 다음과 같이 나열되기 때문에 출력은 13이 됩니다.
-
1."x"가 세 번 나타납니다.
-
"xx"는 한 번 나타납니다.
-
3. "y"가 두 번 나타납니다.
-
"yy"는 한 번 나타납니다.
-
5. "z"가 세 번 나타납니다.
-
"zz"가 두 번 나타납니다.
-
"zzz"는 한 번 나타납니다.
그래서, (3 + 1 + 2 + 1 + 3 + 2 + 1) =13.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
s :=s "@" 연결
-
h:=새 지도
-
이전:=s[0]
-
c:=1
-
인덱스 1에서 끝까지 s의 각 i에 대해 수행
-
prev가 i와 같지 않으면
-
prev*c가 h에 있으면
-
h[이전*c] :=h[이전*c] + 1
-
-
그렇지 않으면
-
h[이전*c]:=1
-
-
c:=1
-
-
prev가 i와 같으면
-
c :=c + 1
-
-
이전 :=나는
-
-
지느러미:=0
-
h의 각 i에 대해 수행
-
t:=i의 크기
-
k:=0
-
t가 0과 같지 않은 동안 수행
-
k :=k + t
-
t :=t - 1
-
-
지느러미 :=지느러미 + k*h[i]
-
-
핀 모드 반환 10^9+7
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(s):
s+="@"
h={}
prev=s[0]
c=1
for i in s[1:]:
if prev!=i:
if prev*c in h:
h[prev*c]+=1
else:
h[prev*c]=1
c=1
if prev == i:
c += 1
prev = i
fin=0
for i in h:
t=len(i)
k=0
while t!=0:
k+=t
t-=1
fin+=k*h[i]
return fin % 1000000007
s = "xyyzzzxx"
print(solve(s)) 입력
"xyyzzzxx"
출력
13