資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學字串在其所有子串中的字典序排名
字串操作是計算機科學中的一個重要主題，它涉及連線、子串、反轉等操作。字串操作中一個有趣的問題是找到一個字串在其所有子串中的字典序排名。在本文中，我們將討論一種使用遞迴和回溯演算法來解決此問題的演算法。
問題陳述
給定一個長度為 N 的字串 S，我們必須在其所有子串中找到 S 的字典序排名。字典序排名定義為字串在其所有子串的字典序排序列表中的位置。
方法
我們可以使用遞迴和回溯的方法來解決這個問題。我們將生成給定字串 S 的所有可能的子串，並跟蹤在字典序中位於 S 之前的子串的數量。
讓我們詳細瞭解一下演算法：
將變數“rank”初始化為 1。
使用遞迴和回溯生成給定字串 S 的所有可能的子串。
對於每個子串，將其與給定字串 S 進行比較，如果子串在字典序中位於 S 之前，則遞增“rank”變數。
返回“rank”變數。
示例
以下是實現上述演算法的程式碼：
#include <stdio.h>
#include <string.h>
// Function to generate all substrings and find their lexicographic rank
void generateSubstrings(const char* s, char* temp, int start, int end, int* rank) {
if (start > end) {
if (strcmp(temp, s) < 0) {
(*rank)++;
}
return;
}
generateSubstrings(s, temp, start + 1, end, rank);
char new_temp[end - start + 2];
strncpy(new_temp, temp, start);
new_temp[start] = s[start];
new_temp[start + 1] = '\0';
generateSubstrings(s, new_temp, start + 1, end, rank);
}
// Function to find the lexicographic rank of a string
int lexicographicRank(const char* s) {
int rank = 1;
generateSubstrings(s, "", 0, strlen(s) - 1, &rank);
return rank;
}
int main() {
const char* s = "abc";
printf("String: %s\n", s);
printf("Lexicographic Rank: %d\n", lexicographicRank(s));
return 0;
}
輸出
String: abc Lexicographic Rank: 8
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
void generateSubstrings(string s, string temp, int start, int end, int& rank) {
if (start > end) {
if (temp < s) {
rank++;
}
return;
}
generateSubstrings(s, temp, start + 1, end, rank);
generateSubstrings(s, temp + s[start], start + 1, end, rank);
}
int lexicographicRank(string s) {
int rank = 1;
generateSubstrings(s, "", 0, s.length() - 1, rank);
return rank;
}
int main() {
string s = "abc";
cout << "String: " << s << endl;
cout << "Lexicographic Rank: " << lexicographicRank(s) << endl;
return 0;
}
輸出
String: abc Lexicographic Rank: 4
public class Main {
// Function to generate all substrings and find their lexicographic rank
static void generateSubstrings(String s, StringBuilder temp, int start, int end, int[] rank) {
if (start > end) {
if (temp.toString().compareTo(s) < 0) {
rank[0]++;
}
return;
}
generateSubstrings(s, temp, start + 1, end, rank);
temp.append(s.charAt(start));
generateSubstrings(s, temp, start + 1, end, rank);
temp.setLength(temp.length() - 1); // Remove the last character from temp
}
// Function to find the lexicographic rank of a string
static int lexicographicRank(String s) {
int[] rank = {1};
generateSubstrings(s, new StringBuilder(), 0, s.length() - 1, rank);
return rank[0];
}
public static void main(String[] args) {
String s = "abc";
System.out.println("String: " + s);
System.out.println("Lexicographic Rank: " + lexicographicRank(s));
}
}
輸出
String: abc Lexicographic Rank: 4
def generate_substrings(s, temp, start, end, rank):
if start > end:
if temp < s:
rank[0] += 1
return
generate_substrings(s, temp, start + 1, end, rank)
generate_substrings(s, temp + s[start], start + 1, end, rank)
def lexicographic_rank(s):
rank = [1]
generate_substrings(s, "", 0, len(s) - 1, rank)
return rank[0]
if __name__ == "__main__":
s = "abc"
print("String:", s)
print("Lexicographic Rank:", lexicographic_rank(s))
輸出
String: abc Lexicographic Rank: 4
測試用例說明
讓我們以字串“abc”為例。我們需要找到其所有子串的字典序排名。
最初，我們有一個空字串，其字典序排名為 1。
子串“a”的字典序排名為 1，因為它在字典序中是第一個子串。
子串“ab”的字典序排名為 2，因為它在字典序中位於“a”之後。
子串“abc”的字典序排名為 4，因為它在字典序中位於“a”、“ab”和“ac”之後。
子串“b”的字典序排名為 3，因為它在字典序中位於“a”之後但位於“c”之前。
子串“bc”的字典序排名為 5，因為它在字典序中位於“ab”和“ac”之後但位於“c”之前。
子串“c”的字典序排名為 6，因為它在字典序中位於“a”、“ab”、“ac”和“b”之後。
因此，“abc”所有子串的字典序排名為：[1, 1, 2, 3, 4, 5, 6]。
結論
在本文中，我們討論了一種使用遞迴和回溯演算法來查詢字串在其所有子串中的字典序排名的演算法。這種方法也可以用來解決其他與字串操作相關的其它問題。
604 次瀏覽
