問題
문자열이 주어졌을 때, 가능한 모든 부분 문자열의 개수를 출력하는 프로그램을 작성하라.
부분 문자열이란 문자열의 임의의 문자를 제거하고 문자열 내의 문자들의 순서를 바꾸지 않았을 때, 얻을 수 있는 문자열을 뜻한다.
예를 들어 "agh"는 "abcdefgh"의 부분 문자열이나, "ahg"는 부분 문자열이 될 수 없다. 그리고 문자열 자체가 문자열의 부분문자열이 될 수 있으며, 길이 0의 문자열의 경우 모든 문자열의 부분 문자열이다.
가능한 모든 문자열을 헤아릴 때 같은 부분 문자열이 존재할 경우 이는 같은 것으로 간주 한다. 가령 "AAA"라는 문자열의 경우 "A"라는 부분 문자열을 만들 수 있는 경우는 3가지가 있지만, 이를 하나로 간주한다는 것이다.
"AAA"의 경우 만들 수 있는 부분 문자열은 "", "A", "AA", "AAA" 4가지를 만들 수 있다.
入力
첫 번째 줄에는 입력에 들어오는 문자열의 개수 T(T≤100)가 입력된다. 그 다음 줄에는 T개의 줄에 T개의 문자열이 입력되며, 문자열의 최대 길이는 100,000이다.
出力
T개의 줄에 입력된 문자열의 순서대로 가능한 부분 문자열의 개수를 출력하는데, 가능한 경우가 많을 수 있기 때문에 1,000,000,007로 나눈 나머지로 출력한다.
例題
3
AAA
ABCDEFG
HANCOM
4
128
64
出典
CodeCraft 08 Distinct Subsequences
ログインしないとコードを書けません。