結果

問題 No.1994 Confusing Name
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-08-25 20:45:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 489 ms / 2,000 ms
コード長 1,128 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 142,552 KB
最終ジャッジ日時 2024-08-25 20:45:33
合計ジャッジ時間 8,978 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,428 KB
testcase_01 AC 38 ms
53,144 KB
testcase_02 AC 39 ms
53,136 KB
testcase_03 AC 35 ms
53,112 KB
testcase_04 AC 38 ms
52,480 KB
testcase_05 AC 83 ms
76,616 KB
testcase_06 AC 108 ms
77,648 KB
testcase_07 AC 63 ms
69,956 KB
testcase_08 AC 91 ms
76,872 KB
testcase_09 AC 96 ms
77,176 KB
testcase_10 AC 96 ms
77,116 KB
testcase_11 AC 80 ms
76,540 KB
testcase_12 AC 356 ms
122,240 KB
testcase_13 AC 451 ms
132,488 KB
testcase_14 AC 414 ms
142,076 KB
testcase_15 AC 361 ms
127,128 KB
testcase_16 AC 355 ms
128,168 KB
testcase_17 AC 356 ms
130,156 KB
testcase_18 AC 451 ms
142,188 KB
testcase_19 AC 489 ms
142,268 KB
testcase_20 AC 463 ms
142,552 KB
testcase_21 AC 186 ms
97,312 KB
testcase_22 AC 116 ms
83,608 KB
testcase_23 AC 424 ms
132,272 KB
testcase_24 AC 394 ms
131,736 KB
testcase_25 AC 271 ms
116,744 KB
testcase_26 AC 170 ms
101,892 KB
testcase_27 AC 396 ms
126,780 KB
testcase_28 AC 279 ms
116,804 KB
testcase_29 AC 105 ms
81,868 KB
testcase_30 AC 300 ms
117,116 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
ss=[]
d={}
B1=1007
M1=1000000007
P1=[1]
for i in range(1,10):
  P1+=[P1[-1]*B1%M1]
B2=1009
M2=1000000009
P2=[1]
for i in range(1,10):
  P2+=[P2[-1]*B2%M2]
for i in range(n):
  s=input()
  h1=0
  h2=0
  for j in range(len(s)):
    h1+=ord(s[j])*P1[j]
    h1%=M1
    h2+=ord(s[j])*P2[j]
    h2%=M2
  h=(h1,h2)
  if h not in d:
    d[h]=0
  d[h]+=1
  for j in range(len(s)):
    h1-=ord(s[j])*P1[j]
    h1+=ord("?")*P1[j]
    h1%=M1
    h2-=ord(s[j])*P2[j]
    h2+=ord("?")*P2[j]
    h2%=M2
    h=(h1,h2)
    if h not in d:
      d[h]=0
    d[h]+=1
    h1-=ord("?")*P1[j]
    h1+=ord(s[j])*P1[j]
    h1%=M1
    h2-=ord("?")*P2[j]
    h2+=ord(s[j])*P2[j]
    h2%=M2
  ss+=[s]
for i in range(n):
  s=ss[i]
  h1=0
  h2=0
  for j in range(len(s)):
    h1+=ord(s[j])*P1[j]
    h1%=M1
    h2+=ord(s[j])*P2[j]
    h2%=M2
  c=0
  for j in range(len(s)):
    h1-=ord(s[j])*P1[j]
    h1+=ord("?")*P1[j]
    h1%=M1
    h2-=ord(s[j])*P2[j]
    h2+=ord("?")*P2[j]
    h2%=M2
    h=(h1,h2)
    c+=d[h]-1
    h1-=ord("?")*P1[j]
    h1+=ord(s[j])*P1[j]
    h1%=M1
    h2-=ord("?")*P2[j]
    h2+=ord(s[j])*P2[j]
    h2%=M2
  print(c)
0