Power Strings
Power Strings
题面翻译
题意简述：
求一个字符串由多少个重复的子串连接而成。
例如 ababab 由三个 ab 连接而成，abcd 由 abcd 由一个 abcd 连接而成。
输入格式
本题多组数据 。
每一组数据仅有一行，这一行仅有一个字符串 s。
输入的结束标志为一个 .。
输出格式
对于每一组数据，输出这组字符串由多少个重复的子串连接而成。
说明/提示
1\le |s|\le 10^6。
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
abcd
aaaa
ababab
.样例输出 #1
1
4
3读题
基于哈希技术的方法中提到，在分析给定字符串时会利用哈希值来识别字符串中的重复子串是否存在，并计算所有重复子串的数量
此题表现优异, 笔者打算将内容分为两个部分进行阐述, 具体包括概述与深入分析. 当然, 在阅读之后有興趣的讀者可以通过網路查閱相關資料（例如《算法競賽入門經典·訓練指南》）.
1.总览
根据题目，很容易想到：
- 读入一个字符串，存储在数组
aa中，作为主串。 - 检查是否为结束标志，即字符串以句号
'.'开头。如果是，则退出程序；否则继续执行后续步骤。 - 计算输入字符串
aa的长度，存储在变量n中。 - 初始化哈希数组
h，数组大小设为M。 - 计算哈希数组
h，其中h[i]表示字符串aa的前缀子串aa[1...i]的哈希值。 - 进入循环遍历，枚举每个可能的重复模式长度
i。 - 判断当前长度
i是否能整除字符串长度n，如果不能，则继续下一次循环。 - 计算模式串的哈希值
s，即子串aa[1...i]的哈希值。 - 调用
check函数，检查字符串是否存在长度为i的重复模式。check函数使用哈希值进行匹配判断。 - 如果存在重复模式，则输出重复模式的个数，即字符串长度除以重复模式长度。
- 回到第 5 步，继续处理下一个输入字符串。
代码
#include<bits/stdc++.h>
using namespace std;
const int x=1311,M=1e7;
int a[M],b[M],h[M],f=0;
char aa[M],bb[M];
int n,s;
bool init(){
scanf("%s",aa+1);
if(aa[1]=='.') return 0;
n=strlen(aa+1);
h[0]=0;
for (int i=1;i<=n;i++) h[i]=h[i-1]*x+int(aa[i]-'A'+1);
return 1;
}
bool check(int v,int k){
for (int i=1;i<=n;i+=k)
if (v!=h[i+k-1]-h[i-1]*a[k]) return 0;
return 1;
}
int main(){
a[0]=1;
for (int i=1;i<=1000000;i++) a[i]=a[i-1]*x;
while (init()){
for (int i=1;i<=n;++i){
if (n%i) continue;
if (i>n/2){cout<<1<<endl;break;}
s=h[i];
if (check(s,i)){
cout<<n/i<<endl;
break;
}
}
}
return 0;
}2.分析
读者已充分阅读并理解了总览与相关代码内容。随后是对该方案的深入分析，在这个过程中可能会有一些关键点需要特别关注。或许会有部分读者感到时间紧迫而有所期待地略过后续内容；然而作为项目的负责人笔者始终致力于全面理解其核心逻辑与实现细节因为该方案具有极为独特的创新性与实用性
check
bool check(int v,int k){
for (int i=1;i<=n;i+=k)
if (v!=h[i+k-1]-h[i-1]*a[k]) return 0;
return 1;
}该函数 check 被用来检测字符串中是否存在长度为特定值的重复子串。开发者倾向于将功能打包以便于复用。
采用循环遍历的方式，并将长度设定为 k 后进行检测，以查看是否存在具有哈希值为 v 的重复子串。
计算当前位置子串的哈希值时，请与预先计算的目标哈希值进行比较：如果当前哈希值与目标哈希值不一致，则可确定此位置不满足条件。
如果在整个遍历过程中均未发现任何不符合条件的情况，则可判定该字符串必定包含至少一个长度为 k 的重复子串。
init
bool init(){
scanf("%s",aa+1);
if(aa[1]=='.') return 0;
n=strlen(aa+1);
h[0]=0;
for (int i=1;i<=n;i++) h[i]=h[i-1]*x+int(aa[i]-'A'+1);
return 1;
}在总览中存在较多的操作项,其中相当一部分属于初始化操作.我们可以通过do-while机制来处理这些操作项.然而,在实践中发现相比而言函数封装是一种更为高效的方式.
需要注意的是hash值的递推计算公式的具体实现细节.上一篇已经进行了详细阐述因此在此不做进一步讨论.
附加代码1
#include <iostream>
#include <string>
using namespace std;
int countRepeatingSubstrings(string s) {
int n = s.length();
for (int i = 1; i <= n / 2; i++) {
if (n % i == 0) {
bool isRepeating = true;
for (int j = i; j < n; j++) {
if (s[j] != s[j % i]) {
isRepeating = false;
break;
}
}
if (isRepeating) {
return n / i;
}
}
}
return 1;
}
int main() {
string s;
cin >> s;
while (s != ".") {
int repeatingCount = countRepeatingSubstrings(s);
cout << repeatingCount << endl;
cin >> s;
}
return 0;
}附加代码2
#include<bits/stdc++.h>
const int M=1e7;
char a[M];int n;
using namespace std;
int f[M],nxt[M];long long ans;
void getfail(){
int j=0;
f[0]=f[1]=0;
for (int i=1;i<n;i++){
while(j and a[i+1]!=a[j+1]) j=f[j];
if (a[i+1]==a[j+1]) j++;
f[i+1]=j;
}
}
int main(){
while (scanf("%s",a+1)==1){
if (a[1]=='.') break;
n=strlen(a+1);
getfail();
if (n%(n-f[n])==0) cout<<n/(n-f[n])<<endl;
else cout<<1<<endl;
}
return 0;
}