資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
