字符串题目记录
字符串题目记录 字符串题目记录是 ACM 题目中的一种常见类型,涉及到字符串处理、哈希、后缀数组、KMP 算法等多种知识点。下面是对标题、描述、标签和部分内容的详细解释和知识点总结。 标题:字符串题目记录 该标题表明了问题的主题是字符串题目记录,可能来自于不同的 OJ 平台,如 POJ、HDU、SPOJ、SGU、HUST 和 FZU 等。 描述:上面可能有 POJ 的题目,HDU 的题目,SPOJ 的题目,SGU 的题目,HUST 上的题目,FZU 上的题目 该描述表明了该题目记录可能来自于不同的 OJ 平台,每个平台都有其特点和难度。 标签:ACM 该标签表明了该题目记录属于 ACM(Algorithmic Competition)领域,涉及到算法竞赛中常见的知识点和解决方法。 部分内容: RKURAL 1486 Equal Squares (最大边长子正方形) 该题目要求找出最大边长重复出现子正方形,使用哈希函数 H(r,c) = H(r-1,c)*P + H(r, c-1)*P - H(r-1,c-1)*P*P + str(r,c),其中 P 是一个质数。该哈希函数可以用于快速计算子矩形的哈希值。 hashRectangle(int r1, int c1, int r2, int c2) = H(r2,c2) - H(r1-1,c2)*P^(r2-r1+1) - H(r2,c1-1)*P^(c2-c1+1) + H(r1-1, c1-1)*P^(r2+c2-r1-c1+2) 该函数用于计算子矩形的哈希值,从而快速判断两个子矩形是否相同。 复杂度分析: 该题目的时间复杂度为 O(logN),其中 N 是矩形的大小。该复杂度来自于二分搜索和哈希函数的计算。 KMPHdu 4333 Revolving Digits (扩展 KMP) 该题目要求找出<=10^5 位的无前导 0 的一个数字 Y,X[i] 表示其循环左移 i 位得到的数字,求这些 X 中小于 Y,=Y,大于 Y 的不同的数字有多少个。 该题目使用 KMP 算法来解决,首先找到字符串的循环节,然后使用 KMP 算法来找出所有循环位移的不同的数字。 HDU 4416 该题目要求找出 A 中有多少个子串不再 B 中出现。该题目使用后缀数组来解决,预处理时间复杂度为 O(|A|+|B|),然后使用二分搜索来找到相应的子串。 HDU 4029 Distinct Sub-matrix 该题目要求找出不同子矩形个数,N,M<=2^7。该题目使用哈希函数来解决,枚举子矩形的列数 w,处理出 h(r,c)= RK( mat[r,c],,,mat[r,c+w-1] ),然后使用后缀数组来找到不同子矩形个数。 HDU 3948 The Number of Palindromes 该题目要求找出长度<=10^5 的不同回文子串个数。该题目使用后缀数组来解决,先将 S 的逆加在 S 的后面,然后遍历后缀数组,找到所有回文子串的个数。 总结来说,字符串题目记录涉及到多种知识点,包括哈希、KMP 算法、后缀数组、循环节、回文串等。这些知识点都是 ACM 领域中常见的解决方法和思想。