#include
#include
#include
#include
using namespace std;
#define MAX_LENGTH 1000 // the max allowed input string length
struct Result { // the structure used to store the function output
int start; // the start position of the longest substring
int length; // the length of the longest substring
};
Result longestSubstring(char* str) {
int lastIndex[256]; // for 8-bit ASCII char
for (int i = 0; i < 256; i++) // initilaize to -1
lastIndex[i] = -1;
size_t n = strlen(str);
int start = 0; // start pos of substr
int length = 1; // length of substr
lastIndex[str[start]] = 0; // mark pos of first letter
Result result = {start, length}; // start = 0, length = 1
for (int i = 1; i < n; i++) {
// if found a repeating char in the current substring
if (lastIndex[str[i]] >= start) {
start = lastIndex[str[i]] + 1;
}
lastIndex[str[i]] = i;
length = i - start + 1;
if (length >= result.length) {
result.length = length;
result.start = start;
}
}
return result;
}
int main(int argc, char** argv) {
int lastIndex[MAX_LENGTH];
char str[MAX_LENGTH]; // buffer
ifstream fin("tut02_input.txt");
if (!fin) {
cout << "Input file not found.";
exit(1);
}
int testcase = 0;
fin >> testcase;
for (int i = 0; i < testcase; i++) {
fin >> str;
Result longest = longestSubstring(str);
cout << "Case " << i + 1 << endl;
printf("The substring (%d,%d) is %.*s\n", longest.start, longest.length,
longest.length, str + longest.start);
cout << endl;
}
fin.close();
return 0;
}
他應該是用下面這個code來判斷有沒有重複? 但是原理是什麼? 不太明白
for (int i = 1; i < strlen(str); i++) {
// if found a repeating char in the current substring
if (lastIndex[str[i]] >= start) {
start = lastIndex[str[i]] + 1;
}
這題是不重覆字元的最長子字串
就你的程式碼來看
做法是由左至右一個一個字元判斷
1.如果重覆(lastIndex[str[i]] >= start
),則重設答案的「起始點」(start)
2.記錄該字元的「位置」(lastIndex[str[i]] = i
)
一開始全部字元都未出現
所以將lastIndex[]
都設為 -1 (因為 start 的初始值是 0)
把你提供的程式加上註解來幫助理解
如下:
#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX_LENGTH 1000 // 最大輸入字符串長度
struct Result // 用來存儲函數輸出的結構體
{
int start; // 最長子串的起始位置
int length; // 最長子串的長度
};
// 找出最長子串的函數
Result longestSubstring(char* str)
{
// lastIndex 數組是用來記錄每個字符最後一次出現的位置的
int lastIndex[256]; // 為 8 位 ASCII 字符
for (int i = 0; i < 256; i++) // 初始化為 -1
lastIndex[i] = -1;
// n 為字符串的長度
size_t n = strlen(str);
int start = 0; // 子串的起始位置
int length = 1; // 子串的長度
lastIndex[str[start]] = 0; // 標記第一個字符的位置
Result result = {start, length}; // 起始位置為 0,長度為 1
for (int i = 1; i < n; i++)
{
// 如果在當前子串中找到了重複的字符
// 舉例來說,假設當前子串是 "abcdefg",
// 這段代碼中的 lastIndex 數組就是用來記錄每個字符最後一次出現的位置的。
// 那麼,當我們遍歷到字符 'd' 時,
// lastIndex['d'] 的值應該是 3(因為 'd' 上一次出現在第 3 個位置)。
if (lastIndex[str[i]] >= start)
{
// 如果當前子串存在重複字符,
// 那麼我們就將子串的开始位置更新為這個字符上一次出現的位置加 1,
// 這樣就可以保證當前子串中不存在重複字符了。
start = lastIndex[str[i]] + 1;
}
// 更新字符的最後一次出現的位置
lastIndex[str[i]] = i;
// 更新子串的長度
length = i - start + 1;
// 如果子串的長度大於之前的結果,更新結果
if (length >= result.length)
{
result.length = length;
result.start = start;
}
}
// 返回結果
return result;
}
int main(int argc, char** argv)
{
// lastIndex 數組是用來記錄每個字符最後一次出現的位置的
int lastIndex[MAX_LENGTH];
char str[MAX_LENGTH]; // 緩衝區
// 讀取輸入文件
ifstream fin("tut02_input.txt");
if (!fin)
{
cout << "未找到輸入文件。";
exit(1);
}
int testcase = 0;
fin >> testcase; // 讀取測試用例數
for (int i = 0; i < testcase; i++)
{
fin >> str; // 讀取字符串
// 找出最長子串
Result longest = longestSubstring(str);
cout << "用例 " << i + 1 << endl;
// 輸出結果
printf("最長子串(%d,%d)是 %.*s\n", longest.start, longest.length,
longest.length, str + longest.start);
cout << endl;
}
fin.close(); // 關閉文件
return 0;
}