数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究检查给定的字符串是否对[1, N]范围内的所有K都是K周期性的
本文旨在实现一个程序，用于检查给定的字符串是否对[1, N]范围内的所有K都是K周期性的。
目的是确定提供的字符串在给定字符串s和整数K的情况下是否为K周期性的。如果一个字符串重复子字符串str[0... k-1]，则称其为k周期性的；例如，字符串“ababab”是2周期性的。如果提供的字符串是k周期性的，则打印Yes；否则，打印No。
如果一个字符字符串可以通过连接至少一个长度为k的另一个字符串的重复来创建，则称其具有周期k。例如，由于字符“xyz”重复了四次，因此字符串“xyzxyzxyzxyz”包含周期三。周期6（“xyzxyz”重复两次）和12（“xyzxyzxyzxyz”重复一次）也包括在内。
示例
Input: N = 7 and the string S = "xyzxyzx" Output: 3 6 7
解释
取前缀“x”，其长度为1。如果我们重复它以创建一个长度为7的字符串，我们将得到“xxxxxx”，它与原始字符串不同。
如果我们重复长度为2的前缀（在本例中为“xy”）以创建一个长度为7的字符串，我们将得到“xyxyxyx”，它与原始字符串不同。
假设长度为3的前缀（例如“xyz”），然后重复它以创建一个长度为7的字符串（得到“xyzxyzx”）。此字符串与初始字符串相同。
让我们取一个长度为4的前缀（即“xyzx”)，并重复它以创建一个长度为7的字符串（即“xyzxxyz”)。此字符串与初始字符串不同。
让我们取一个长度为5的前缀（即“xyzxy”)，并重复它以创建一个长度为7的字符串（即“xyzxyxy”)。此字符串与初始字符串不同。
让我们取一个长度为6的前缀（即“xyzxyz”)，并重复它以创建一个长度为7的字符串（即“xyzxyzx”)。此字符串与初始字符串相同。
如果我们重复前缀“xyzxyzx”以创建一个长度为7的字符串，我们将得到“xyzxyzx”，它与初始字符串相同。
问题陈述
实现一个程序，用于检查给定的字符串是否对[1, N]范围内的所有K都是K周期性的。
方法
让我们深入了解Z算法或线性时间模式搜索算法的具体内容。
此技术在线性时间内在文本中找到模式的每个实例。如果文本的长度为n，模式的长度为m，则所需的时间总复杂度为O(m + n)，空间复杂度为线性。现在可以清楚地看到，KMP方法具有相同的时空复杂度，但更容易理解。
在此算法中，创建一个Z数组。
现在让我们描述Z数组。
Z数组与该字符串的字符串str[0...n-1]具有相同的长度。Z数组的元素Z[i]存储了以str[i]开头的最大子字符串的长度，该子字符串也是str[0...n-1]的前缀。由于整个字符串始终是其自身的前缀，因此Z数组中的第一个条目意义不大。
算法
下面给出了获得一个程序以检查给定的字符串是否对[1, N]范围内的所有K都是K周期性的算法
步骤1 - 让我们使用提供的字符串构建一个Z数组。（0索引）
步骤2 - 如果'i'是字符串的周期之一，则长度为(N-i)的后缀与长度为(n-i)的前缀完全对应，因此如果'i'是周期，则(N-i)应该等于位置i处的z值。
步骤3 - 最后，将N（给定字符串的长度）添加到解决方案中；N数很简单，但前面概述的方法无法找到它。
步骤4 - 打印输出。
示例：C程序
以下是上述算法的C程序实现，用于检查给定的字符串是否对[1, N]范围内的所有K都是K周期性的
#include <stdio.h>
#include <string.h>
void getZarr(char *str, int Z[]);
void findPeriod(char *text) {
int l = strlen(text);
int Z[l];
getZarr(text, Z);
for (int i = 1; i < l; ++i) {
if (Z[i] == (l - i))
printf("%d ", i);
}
printf("%d\n", l);
}
void getZarr(char *str, int Z[]) {
int n = strlen(str);
int L, R, k;
L = R = 0;
for (int i = 1; i < n; ++i) {
if (i > R) {
L = R = i;
while (R < n && str[R - L] == str[R])
R++;
Z[i] = R - L;
R--;
} else {
k = i - L;
if (Z[k] < R - i + 1)
Z[i] = Z[k];
else {
L = i;
while (R < n && str[R - L] == str[R])
R++;
Z[i] = R - L;
R--;
}
}
}
}
int main() {
char text[] = "xyzxyzx";
findPeriod(text);
return 0;
}
输出
3 6 7
结论
同样，我们可以获得一个程序，用于检查给定的字符串是否对[1, N]范围内的所有K都是K周期性的。本文解决了获得检查给定字符串是否对[1, N]范围内的所有K都是K周期性的程序的挑战。
这里提供了C编程代码以及实现C程序以检查给定字符串是否对[1, N]范围内的所有K都是K周期性的算法和方法。
210 次查看
