結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 2024-04-19 13:38:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 463 ms / 2,000 ms |
コード長 | 1,714 bytes |
コンパイル時間 | 1,058 ms |
コンパイル使用メモリ | 81,856 KB |
実行使用メモリ | 108,060 KB |
最終ジャッジ日時 | 2024-10-11 06:02:52 |
合計ジャッジ時間 | 6,835 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
A=input()B=input()boundA=[0]boundB=[0]for i in range(1,len(A)):if not A[i] in "*?":boundA.append(i)boundA.append(len(A))for i in range(1,len(B)):if not B[i] in "*?":boundB.append(i)boundB.append(len(B))A=[A[i:j] for i,j in zip(boundA,boundA[1:])]B=[B[i:j] for i,j in zip(boundB,boundB[1:])]leA=len(A)leB=len(B)inf=1<<30dp=[[inf]*(leB+1) for a in range(leA+1)]dp[0][0]=0for i in range(leA+1):for j in range(leB+1):if i:dp[i][j]=min(dp[i][j],dp[i-1][j]+1)if len(A[i-1])==2 and A[i-1][1] in "?*":dp[i][j]=min(dp[i][j],dp[i-1][j])if j:dp[i][j]=min(dp[i][j],dp[i][j-1]+1)if len(B[j-1])==2 and B[j-1][1] in "?*":dp[i][j]=min(dp[i][j],dp[i][j-1])if i and j:dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1)if A[i-1]==B[j-1]:dp[i][j]=min(dp[i][j],dp[i-1][j-1])if len(A[i-1])==2 and A[i-1][1]=="?" and A[i-1][0]==B[j-1]:dp[i][j]=min(dp[i][j],dp[i-1][j-1])if len(B[j-1])==2 and B[j-1][1]=="?" and B[j-1][0]==A[i-1]:dp[i][j]=min(dp[i][j],dp[i-1][j-1])if len(A[i-1])==2 and A[i-1][1]=="*" and A[i-1][0]==B[j-1]:dp[i][j]=min(dp[i][j],dp[i-1][j-1])if len(B[j-1])==2 and B[j-1][1]=="*" and B[j-1][0]==A[i-1]:dp[i][j]=min(dp[i][j],dp[i-1][j-1])if len(A[i-1])==2 and A[i-1][1]=="*" and A[i-1][0]==B[j-1]:dp[i][j]=min(dp[i][j],dp[i][j-1])if len(B[j-1])==2 and B[j-1][1]=="*" and B[j-1][0]==A[i-1]:dp[i][j]=min(dp[i][j],dp[i-1][j])ans=dp[leA][leB]print(ans)