字符串编码

字符串编码

day1里的T1。

字符串哈希+暴力。

对S,T这两个字符串进行哈希,令数字0...25表示小写字母a...z,设f[i][j]表示串S前i位的j字符的哈希值,g[i]表示串T的i字符的哈希值。那么对于一个从x起始的S的子串,若选中字符i,j,此子串与T匹配的充要条件是S[x+|T|-1][i]-S[x-1][i]=T[j]且S[x+|T|-1][j]-S[x-1][j]=T[i]。

在判断时只需枚举每个起始位置,枚举两个字符i,j,判断选中i,j能否使S的子串与T匹配即可。

时间复杂度

继续阅读字符串编码