功課的答案不太明白 c++ 我看不懂如何找到Substring

c++

sintsun 2022-01-30 01:59:28 ‧ 1868 瀏覽

分享至

#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;
    }

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

2 個回答

海綿寶寶

iT邦大神 1 級 ‧ 2022-01-30 14:27:19

這題是不重覆字元的最長子字串

光在 iT邦幫忙就有兩篇解答
解答一
 解答二

就你的程式碼來看
做法是由左至右一個一個字元判斷
1.如果重覆(lastIndex[str[i]] >= start)，則重設答案的「起始點」(start)
2.記錄該字元的「位置」(lastIndex[str[i]] = i)

一開始全部字元都未出現
所以將lastIndex[]都設為 -1 (因為 start 的初始值是 0)

回應
分享
檢舉

登入發表回應

JamesDoge

iT邦高手 1 級 ‧ 2023-01-08 01:47:02

把你提供的程式加上註解來幫助理解
如下:

#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;
}