Python을 사용하여 1만 있는 부분 문자열의 수를 찾는 프로그램

<시간/>

이진 문자열 s가 있다고 가정합니다. 모든 문자가 1인 부분 문자열의 수를 찾아야 합니다. 답변이 매우 클 수 있으므로 결과 모드 10^9 + 7을 반환합니다.

따라서 입력이 s ="1011010"과 같으면 출력은 5가 됩니다. 왜냐하면 1. 네 번 "1" 2. 한 번 "11"이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=10^9+7
결과 :=0
div :='0'을 사용하여 분할하여 이진 문자열을 나눕니다.
div의 각 x에 대해 수행
- x가 비어 있으면 다음 반복으로 이동
- 결과 :=결과 + (x의 크기 *(x의 크기 +1))/2의 몫
반환 결과 모드 m

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

def solve(s):
   m = 10**9+7
   result = 0
   for x in s.split('0'):
      if not x: continue
      result += (len(x)*(len(x)+1)) // 2
   return result % m
s = "1011010"
print(solve(s))

입력

"1011010"