-
Notifications
You must be signed in to change notification settings - Fork 1
/
wordCombinations.py
69 lines (49 loc) · 1.11 KB
/
wordCombinations.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import sys
import operator
N,M = (5000005,30)
trie = [[0]*M]*N
isEnd = [False]*N
dp = [-1]*N
counter = 0
MOD = 100000007
def wordCombinations(index, s):
if index == len(s):
dp[index]=1
return dp[index]
node = 0
ans = 0
for i in range(index,len(s)):
character = ord(s[i])-97
if not trie[node][character]:
dp[index]=ans
return dp[index]
if isEnd[node]:
if dp[i+1] != -1:
ans = (ans + dp[i+1])%MOD
else:
ans = (ans + wordCombinations(index+1,s))%MOD
dp[index]=ans;
return dp[index]
def insert(str):
curr = 0
global counter
#print(str)
for i in str:
character = ord(i)-97
if character < 0:
break
#print(character)
if not trie[curr][character]:
counter = operator.add(counter,1)
trie[curr][character] = counter
curr = trie[curr][character]
isEnd[curr]=True
k=0
s = input("\n")
k = int(input())
i=0
while i < k:
str = input()
insert(str)
i += 1
print(wordCombinations(0,s))