結果

問題 No.1994 Confusing Name
コンテスト
ユーザー sasa8uyauya
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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