Qt中QString 查找子串的多种方法

#include <qstring>
#include <qdebug>

void basicfindmethods()
{
    qstring str = "hello, world! this is a test string.";
    
    // 1.1 contains() - 检查是否包含子串
    bool containshello = str.contains("hello");
    bool containsworld = str.contains("world");
    bool containstest = str.contains("test");
    bool containsmissing = str.contains("missing");
    
    qdebug() << "包含 'hello':" << containshello;      // true
    qdebug() << "包含 'world':" << containsworld;      // true
    qdebug() << "包含 'test':" << containstest;        // true
    qdebug() << "包含 'missing':" << containsmissing;  // false
    
    // 1.2 大小写敏感控制
    bool containshellocasesensitive = str.contains("hello", qt::casesensitive);
    bool containshellocaseinsensitive = str.contains("hello", qt::caseinsensitive);
    
    qdebug() << "区分大小写查找 'hello':" << containshellocasesensitive;    // false
    qdebug() << "不区分大小写查找 'hello':" << containshellocaseinsensitive; // true
    
    // 1.3 使用正则表达式
    bool containsdigits = str.contains(qregularexpression("\\d+"));
    bool containsword = str.contains(qregularexpression("\\btest\\b"));
    
    qdebug() << "包含数字:" << containsdigits;  // false
    qdebug() << "包含完整单词 'test':" << containsword;  // true
}

void findpositions()
{
    qstring str = "the quick brown fox jumps over the lazy dog. the fox is brown.";
    
    // 2.1 indexof() - 查找第一次出现的位置
    int pos1 = str.indexof("fox");
    int pos2 = str.indexof("fox", 20);  // 从位置20开始查找
    int pos3 = str.indexof("cat");      // 未找到返回-1
    
    qdebug() << "'fox' 第一次出现位置:" << pos1;  // 16
    qdebug() << "从位置20开始查找 'fox':" << pos2;  // 44
    qdebug() << "'cat' 的位置:" << pos3;  // -1
    
    // 2.2 lastindexof() - 查找最后一次出现的位置
    int lastpos1 = str.lastindexof("fox");
    int lastpos2 = str.lastindexof("fox", 30);  // 在位置30之前查找
    
    qdebug() << "'fox' 最后一次出现位置:" << lastpos1;  // 44
    qdebug() << "在位置30之前查找 'fox':" << lastpos2;  // 16
    
    // 2.3 大小写敏感控制
    int poscasesensitive = str.indexof("the");
    int poscaseinsensitive = str.indexof("the", 0, qt::caseinsensitive);
    
    qdebug() << "区分大小写查找 'the':" << poscasesensitive;      // 0
    qdebug() << "不区分大小写查找 'the':" << poscaseinsensitive;  // 32
}

void countoccurrences()
{
    qstring str = "apple banana apple orange apple grape apple";
    
    // 3.1 count() - 统计子串出现次数
    int applecount = str.count("apple");
    int bananacount = str.count("banana");
    int orangecount = str.count("orange");
    int missingcount = str.count("pear");
    
    qdebug() << "'apple' 出现次数:" << applecount;    // 4
    qdebug() << "'banana' 出现次数:" << bananacount;  // 1
    qdebug() << "'orange' 出现次数:" << orangecount;  // 1
    qdebug() << "'pear' 出现次数:" << missingcount;   // 0
    
    // 3.2 大小写敏感控制
    int applecasesensitive = str.count("apple", qt::casesensitive);
    int applecaseinsensitive = str.count("apple", qt::caseinsensitive);
    
    qdebug() << "区分大小写统计 'apple':" << applecasesensitive;    // 0
    qdebug() << "不区分大小写统计 'apple':" << applecaseinsensitive; // 4
    
    // 3.3 统计字符出现次数
    int acount = str.count('a');
    int pcount = str.count('p');
    
    qdebug() << "字符 'a' 出现次数:" << acount;  // 8
    qdebug() << "字符 'p' 出现次数:" << pcount;  // 8
}

#include <qvector>

void findalloccurrences()
{
    qstring str = "abracadabra abra kadabra";
    qstring sub = "abra";
    
    // 4.1 查找所有出现位置
    qvector<int> positions;
    int pos = 0;
    
    while ((pos = str.indexof(sub, pos)) != -1) {
        positions.append(pos);
        pos += sub.length();  // 移动到下一个位置
    }
    
    qdebug() << "'abra' 的所有位置:";
    for (int p : positions) {
        qdebug() << "  位置:" << p << ", 子串:" << str.mid(p, sub.length());
    }
    
    // 4.2 查找重叠的子串
    qstring str2 = "aaaaa";
    qstring sub2 = "aa";
    qvector<int> overlappingpositions;
    
    pos = 0;
    while ((pos = str2.indexof(sub2, pos)) != -1) {
        overlappingpositions.append(pos);
        pos += 1;  // 只移动1位，允许重叠
    }
    
    qdebug() << "'aa' 在 'aaaaa' 中的所有位置(允许重叠):";
    for (int p : overlappingpositions) {
        qdebug() << "  位置:" << p;
    }
}

#include <qregularexpression>
#include <qregularexpressionmatch>

void regexfindmethods()
{
    qstring str = "email: test@example.com, phone: 123-456-7890, date: 2023-12-20";
    
    // 5.1 查找匹配
    qregularexpression emailregex(r"(\b[a-za-z0-9._%+-]+@[a-za-z0-9.-]+\.[a-z|a-z]{2,}\b)");
    qregularexpressionmatch emailmatch = emailregex.match(str);
    
    if (emailmatch.hasmatch()) {
        qstring email = emailmatch.captured(0);
        qdebug() << "找到邮箱:" << email;
        qdebug() << "起始位置:" << emailmatch.capturedstart();
        qdebug() << "结束位置:" << emailmatch.capturedend();
    }
    
    // 5.2 查找电话号码
    qregularexpression phoneregex(r"(\b\d{3}[-.]?\d{3}[-.]?\d{4}\b)");
    qregularexpressionmatch phonematch = phoneregex.match(str);
    
    if (phonematch.hasmatch()) {
        qdebug() << "找到电话:" << phonematch.captured(0);
    }
    
    // 5.3 查找所有匹配
    qregularexpression dateregex(r"(\b\d{4}-\d{2}-\d{2}\b)");
    qregularexpressionmatchiterator dateiterator = dateregex.globalmatch(str);
    
    qdebug() << "所有日期:";
    while (dateiterator.hasnext()) {
        qregularexpressionmatch match = dateiterator.next();
        qdebug() << "  " << match.captured(0) << "在位置" << match.capturedstart();
    }
    
    // 5.4 捕获组
    qstring logline = "2023-12-20 14:30:25 [info] user login successful";
    qregularexpression logregex(r"((\d{4}-\d{2}-\d{2}) (\d{2}:\d{2}:\d{2}) \[(\w+)\] (.+))");
    qregularexpressionmatch logmatch = logregex.match(logline);
    
    if (logmatch.hasmatch()) {
        qdebug() << "日志解析:";
        qdebug() << "  日期:" << logmatch.captured(1);
        qdebug() << "  时间:" << logmatch.captured(2);
        qdebug() << "  级别:" << logmatch.captured(3);
        qdebug() << "  消息:" << logmatch.captured(4);
    }
}

void findandreplace()
{
    qstring str = "the quick brown fox jumps over the lazy dog.";
    
    // 6.1 replace() - 简单替换
    qstring replaced1 = str;
    replaced1.replace("fox", "cat");
    qdebug() << "替换 'fox' 为 'cat':" << replaced1;
    
    // 6.2 替换所有出现
    qstring str2 = "apple apple orange apple";
    qstring replaced2 = str2;
    replaced2.replace("apple", "pear");
    qdebug() << "替换所有 'apple' 为 'pear':" << replaced2;
    
    // 6.3 使用正则表达式替换
    qstring html = "<p>hello <b>world</b>!</p>";
    qregularexpression tagregex(r"(<[^>]*>)");
    qstring textonly = html;
    textonly.replace(tagregex, "");
    qdebug() << "移除html标签:" << textonly;
    
    // 6.4 使用lambda进行复杂替换
    qstring numbers = "1, 2, 3, 4, 5";
    qregularexpression numregex(r"(\d+)");
    qstring doubled = numbers;
    doubled.replace(numregex, const qregularexpressionmatch &match {
        int num = match.captured(0).toint();
        return qstring::number(num * 2);
    });
    qdebug() << "数字加倍:" << doubled;
}

// stringfinder.h
#ifndef stringfinder_h
#define stringfinder_h

#include <qstring>
#include <qvector>
#include <qregularexpression>
#include <qpair>

class stringfinder
{
public:
    // 查找单个子串的所有出现
    static qvector<int> findall(const qstring& text, 
                               const qstring& substring, 
                               qt::casesensitivity cs = qt::casesensitive);
    
    // 查找多个子串的所有出现
    static qvector<qpair<qstring, int>> findallmultiple(const qstring& text, 
                                                       const qstringlist& substrings,
                                                       qt::casesensitivity cs = qt::casesensitive);
    
    // 使用正则表达式查找
    static qvector<qregularexpressionmatch> findallregex(const qstring& text, 
                                                        const qregularexpression& regex);
    
    // 统计子串出现次数
    static int countoccurrences(const qstring& text, 
                               const qstring& substring, 
                               qt::casesensitivity cs = qt::casesensitive);
    
    // 查找最长的公共子串
    static qstring findlongestcommonsubstring(const qstring& str1, 
                                             const qstring& str2);
    
    // 查找最长的重复子串
    static qstring findlongestrepeatedsubstring(const qstring& text);
    
    // 查找所有单词及其位置
    static qvector<qpair<qstring, int>> findallwords(const qstring& text);
    
    // 模糊查找（支持通配符）
    static qvector<int> fuzzyfind(const qstring& text, 
                                 const qstring& pattern, 
                                 qt::casesensitivity cs = qt::casesensitive);
    
    // 查找并高亮显示
    static qstring highlightall(const qstring& text, 
                               const qstring& substring, 
                               const qstring& starttag = "<mark>",
                               const qstring& endtag = "</mark>",
                               qt::casesensitivity cs = qt::casesensitive);
    
private:
    // 计算编辑距离（用于模糊匹配）
    static int editdistance(const qstring& s1, const qstring& s2);
    
    // 构建后缀数组
    static qvector<int> buildsuffixarray(const qstring& text);
};

#endif // stringfinder_h

// stringfinder.cpp
#include "stringfinder.h"
#include <qdebug>
#include <algorithm>

qvector<int> stringfinder::findall(const qstring& text, 
                                  const qstring& substring, 
                                  qt::casesensitivity cs)
{
    qvector<int> positions;
    
    if (substring.isempty() || text.isempty()) {
        return positions;
    }
    
    int pos = 0;
    while ((pos = text.indexof(substring, pos, cs)) != -1) {
        positions.append(pos);
        pos += substring.length();
    }
    
    return positions;
}

qvector<qpair<qstring, int>> stringfinder::findallmultiple(const qstring& text, 
                                                          const qstringlist& substrings,
                                                          qt::casesensitivity cs)
{
    qvector<qpair<qstring, int>> results;
    
    for (const qstring& sub : substrings) {
        qvector<int> positions = findall(text, sub, cs);
        for (int pos : positions) {
            results.append(qmakepair(sub, pos));
        }
    }
    
    // 按位置排序
    std::sort(results.begin(), results.end(), 
              const qpair<qstring, int>& a, const qpair<qstring, int>& b {
                  return a.second < b.second;
              });
    
    return results;
}

qvector<qregularexpressionmatch> stringfinder::findallregex(const qstring& text, 
                                                           const qregularexpression& regex)
{
    qvector<qregularexpressionmatch> matches;
    
    if (!regex.isvalid()) {
        qwarning() << "无效的正则表达式:" << regex.errorstring();
        return matches;
    }
    
    qregularexpressionmatchiterator iterator = regex.globalmatch(text);
    while (iterator.hasnext()) {
        matches.append(iterator.next());
    }
    
    return matches;
}

int stringfinder::countoccurrences(const qstring& text, 
                                  const qstring& substring, 
                                  qt::casesensitivity cs)
{
    if (substring.isempty()) {
        return 0;
    }
    
    int count = 0;
    int pos = 0;
    
    while ((pos = text.indexof(substring, pos, cs)) != -1) {
        count++;
        pos += substring.length();
    }
    
    return count;
}

qstring stringfinder::findlongestcommonsubstring(const qstring& str1, 
                                                const qstring& str2)
{
    int m = str1.length();
    int n = str2.length();
    
    if (m == 0 || n == 0) {
        return qstring();
    }
    
    // 创建dp表
    qvector<qvector<int>> dp(m + 1, qvector<int>(n + 1, 0));
    int maxlength = 0;
    int endpos = 0;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxlength) {
                    maxlength = dp[i][j];
                    endpos = i;
                }
            }
        }
    }
    
    if (maxlength == 0) {
        return qstring();
    }
    
    return str1.mid(endpos - maxlength, maxlength);
}

qstring stringfinder::findlongestrepeatedsubstring(const qstring& text)
{
    int n = text.length();
    
    if (n < 2) {
        return qstring();
    }
    
    // 构建后缀数组
    qvector<int> suffixarray = buildsuffixarray(text);
    
    // 查找最长公共前缀
    qstring longest = "";
    
    for (int i = 0; i < n - 1; i++) {
        int idx1 = suffixarray[i];
        int idx2 = suffixarray[i + 1];
        
        // 查找公共前缀
        int k = 0;
        while (idx1 + k < n && idx2 + k < n && 
               text[idx1 + k] == text[idx2 + k]) {
            k++;
        }
        
        if (k > longest.length()) {
            longest = text.mid(idx1, k);
        }
    }
    
    return longest;
}

qvector<qpair<qstring, int>> stringfinder::findallwords(const qstring& text)
{
    qvector<qpair<qstring, int>> words;
    
    qregularexpression wordregex(r"(\b\w+\b)");
    qregularexpressionmatchiterator iterator = wordregex.globalmatch(text);
    
    while (iterator.hasnext()) {
        qregularexpressionmatch match = iterator.next();
        qstring word = match.captured(0);
        int pos = match.capturedstart();
        words.append(qmakepair(word, pos));
    }
    
    return words;
}

qvector<int> stringfinder::fuzzyfind(const qstring& text, 
                                    const qstring& pattern, 
                                    qt::casesensitivity cs)
{
    qvector<int> positions;
    
    if (pattern.isempty() || text.isempty()) {
        return positions;
    }
    
    qstring patternlower = (cs == qt::caseinsensitive) ? pattern.tolower() : pattern;
    qstring textlower = (cs == qt::caseinsensitive) ? text.tolower() : text;
    
    // 简单的模糊匹配：检查是否包含所有字符（按顺序）
    for (int i = 0; i <= text.length() - pattern.length(); i++) {
        bool found = true;
        int patternindex = 0;
        
        for (int j = i; j < text.length() && patternindex < pattern.length(); j++) {
            if (textlower[j] == patternlower[patternindex]) {
                patternindex++;
            }
        }
        
        if (patternindex == pattern.length()) {
            positions.append(i);
        }
    }
    
    return positions;
}

qstring stringfinder::highlightall(const qstring& text, 
                                  const qstring& substring, 
                                  const qstring& starttag,
                                  const qstring& endtag,
                                  qt::casesensitivity cs)
{
    if (substring.isempty()) {
        return text;
    }
    
    qstring result = text;
    qvector<int> positions = findall(text, substring, cs);
    
    // 从后往前插入标签，避免位置偏移
    for (int i = positions.size() - 1; i >= 0; i--) {
        int pos = positions[i];
        result.insert(pos + substring.length(), endtag);
        result.insert(pos, starttag);
    }
    
    return result;
}

int stringfinder::editdistance(const qstring& s1, const qstring& s2)
{
    int m = s1.length();
    int n = s2.length();
    
    qvector<qvector<int>> dp(m + 1, qvector<int>(n + 1));
    
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + qmin(qmin(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
            }
        }
    }
    
    return dp[m][n];
}

qvector<int> stringfinder::buildsuffixarray(const qstring& text)
{
    int n = text.length();
    qvector<int> suffixarray(n);
    
    // 初始化后缀数组
    for (int i = 0; i < n; i++) {
        suffixarray[i] = i;
    }
    
    // 简单排序（对于大文本，应使用更高效的算法）
    std::sort(suffixarray.begin(), suffixarray.end(),
              int a, int b {
                  return text.mid(a) < text.mid(b);
              });
    
    return suffixarray;
}

#include "stringfinder.h"
#include <qfile>
#include <qtextstream>
#include <qdatetime>

class loganalyzer
{
public:
    struct logentry {
        qdatetime timestamp;
        qstring level;
        qstring message;
        int linenumber;
    };
    
    qvector<logentry> parselogfile(const qstring& filepath)
    {
        qvector<logentry> entries;
        
        qfile file(filepath);
        if (!file.open(qiodevice::readonly | qiodevice::text)) {
            qwarning() << "无法打开日志文件:" << filepath;
            return entries;
        }
        
        qtextstream in(&file);
        int linenumber = 0;
        
        // 日志格式: [2023-12-20 14:30:25] [info] message here
        qregularexpression logregex(r"(\[(\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2})\] \[(\w+)\] (.+))");
        
        while (!in.atend()) {
            qstring line = in.readline();
            linenumber++;
            
            qregularexpressionmatch match = logregex.match(line);
            if (match.hasmatch()) {
                logentry entry;
                entry.timestamp = qdatetime::fromstring(match.captured(1), "yyyy-mm-dd hh:mm:ss");
                entry.level = match.captured(2);
                entry.message = match.captured(3);
                entry.linenumber = linenumber;
                
                entries.append(entry);
            }
        }
        
        file.close();
        return entries;
    }
    
    qvector<logentry> searchinlogs(const qvector<logentry>& entries, 
                                  const qstring& searchterm,
                                  qt::casesensitivity cs = qt::caseinsensitive)
    {
        qvector<logentry> results;
        
        for (const logentry& entry : entries) {
            if (entry.message.contains(searchterm, cs) ||
                entry.level.contains(searchterm, cs)) {
                results.append(entry);
            }
        }
        
        return results;
    }
    
    qvector<logentry> searchbyregex(const qvector<logentry>& entries,
                                   const qregularexpression& regex)
    {
        qvector<logentry> results;
        
        for (const logentry& entry : entries) {
            if (regex.match(entry.message).hasmatch() ||
                regex.match(entry.level).hasmatch()) {
                results.append(entry);
            }
        }
        
        return results;
    }
    
    qmap<qstring, int> countbylevel(const qvector<logentry>& entries)
    {
        qmap<qstring, int> counts;
        
        for (const logentry& entry : entries) {
            counts[entry.level]++;
        }
        
        return counts;
    }
};

class textsearchtool
{
public:
    struct searchresult {
        int linenumber;
        int position;
        qstring line;
        qstring matchedtext;
    };
    
    qvector<searchresult> searchinfile(const qstring& filepath, 
                                      const qstring& searchterm,
                                      qt::casesensitivity cs = qt::casesensitive)
    {
        qvector<searchresult> results;
        
        qfile file(filepath);
        if (!file.open(qiodevice::readonly | qiodevice::text)) {
            return results;
        }
        
        qtextstream in(&file);
        int linenumber = 0;
        
        while (!in.atend()) {
            qstring line = in.readline();
            linenumber++;
            
            int pos = 0;
            while ((pos = line.indexof(searchterm, pos, cs)) != -1) {
                searchresult result;
                result.linenumber = linenumber;
                result.position = pos;
                result.line = line;
                result.matchedtext = searchterm;
                
                results.append(result);
                
                pos += searchterm.length();
            }
        }
        
        file.close();
        return results;
    }
    
    qvector<searchresult> searchwithregex(const qstring& filepath,
                                         const qregularexpression& regex)
    {
        qvector<searchresult> results;
        
        qfile file(filepath);
        if (!file.open(qiodevice::readonly | qiodevice::text)) {
            return results;
        }
        
        qtextstream in(&file);
        int linenumber = 0;
        
        while (!in.atend()) {
            qstring line = in.readline();
            linenumber++;
            
            qregularexpressionmatchiterator iterator = regex.globalmatch(line);
            while (iterator.hasnext()) {
                qregularexpressionmatch match = iterator.next();
                
                searchresult result;
                result.linenumber = linenumber;
                result.position = match.capturedstart();
                result.line = line;
                result.matchedtext = match.captured();
                
                results.append(result);
            }
        }
        
        file.close();
        return results;
    }
    
    qstring highlightmatches(const qstring& text, 
                            const qvector<searchresult>& results,
                            const qstring& starttag = "<span style='background-color: yellow;'>",
                            const qstring& endtag = "</span>")
    {
        qstring highlighted = text;
        
        // 从后往前插入标签，避免位置偏移
        for (int i = results.size() - 1; i >= 0; i--) {
            const searchresult& result = results[i];
            highlighted.insert(result.position + result.matchedtext.length(), endtag);
            highlighted.insert(result.position, starttag);
        }
        
        return highlighted;
    }
};

#include <qhash>
#include <qset>

class efficientstringsearcher
{
public:
    // boyer-moore算法实现
    static qvector<int> boyermooresearch(const qstring& text, 
                                        const qstring& pattern,
                                        qt::casesensitivity cs = qt::casesensitive)
    {
        qvector<int> positions;
        
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0 || n == 0 || m > n) {
            return positions;
        }
        
        // 预处理坏字符表
        qhash<qchar, int> badchar;
        for (int i = 0; i < m - 1; i++) {
            badchar[pattern[i]] = m - 1 - i;
        }
        
        // 搜索
        int s = 0;
        while (s <= n - m) {
            int j = m - 1;
            
            // 从右向左比较
            while (j >= 0) {
                qchar textchar = (cs == qt::caseinsensitive) ? 
                                 text[s + j].tolower() : text[s + j];
                qchar patternchar = (cs == qt::caseinsensitive) ? 
                                   pattern[j].tolower() : pattern[j];
                
                if (textchar != patternchar) {
                    break;
                }
                j--;
            }
            
            if (j < 0) {
                // 找到匹配
                positions.append(s);
                s += (s + m < n) ? badchar.value(text[s + m], m) : 1;
            } else {
                // 根据坏字符规则移动
                qchar badcharvalue = (cs == qt::caseinsensitive) ? 
                                    text[s + j].tolower() : text[s + j];
                int shift = badchar.value(badcharvalue, m);
                s += qmax(1, shift - (m - 1 - j));
            }
        }
        
        return positions;
    }
    
    // kmp算法实现
    static qvector<int> kmpsearch(const qstring& text, 
                                 const qstring& pattern,
                                 qt::casesensitivity cs = qt::casesensitive)
    {
        qvector<int> positions;
        
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0 || n == 0 || m > n) {
            return positions;
        }
        
        // 构建部分匹配表
        qvector<int> lps(m, 0);
        int len = 0;
        int i = 1;
        
        while (i < m) {
            qchar c1 = (cs == qt::caseinsensitive) ? pattern[i].tolower() : pattern[i];
            qchar c2 = (cs == qt::caseinsensitive) ? pattern[len].tolower() : pattern[len];
            
            if (c1 == c2) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        // 搜索
        i = 0;  // text的索引
        int j = 0;  // pattern的索引
        
        while (i < n) {
            qchar textchar = (cs == qt::caseinsensitive) ? text[i].tolower() : text[i];
            qchar patternchar = (cs == qt::caseinsensitive) ? pattern[j].tolower() : pattern[j];
            
            if (textchar == patternchar) {
                i++;
                j++;
            }
            
            if (j == m) {
                // 找到匹配
                positions.append(i - j);
                j = lps[j - 1];
            } else if (i < n && textchar != patternchar) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return positions;
    }
    
    // 多模式搜索（aho-corasick算法）
    class ahocorasick
    {
    public:
        struct node {
            qhash<qchar, int> next;
            int fail = 0;
            qvector<int> output;
        };
        
        ahocorasick() {
            nodes.append(node());  // 根节点
        }
        
        void addpattern(const qstring& pattern, int patternid) {
            int current = 0;
            
            for (qchar ch : pattern) {
                if (!nodes[current].next.contains(ch)) {
                    nodes[current].next[ch] = nodes.size();
                    nodes.append(node());
                }
                current = nodes[current].next[ch];
            }
            
            nodes[current].output.append(patternid);
        }
        
        void buildfailurelinks() {
            qqueue<int> queue;
            
            // 第一层的失败链接指向根节点
            for (auto it = nodes[0].next.begin(); it != nodes[0].next.end(); ++it) {
                int nextnode = it.value();
                nodes[nextnode].fail = 0;
                queue.enqueue(nextnode);
            }
            
            while (!queue.isempty()) {
                int current = queue.dequeue();
                
                for (auto it = nodes[current].next.begin(); it != nodes[current].next.end(); ++it) {
                    qchar ch = it.key();
                    int child = it.value();
                    
                    int fail = nodes[current].fail;
                    while (fail != 0 && !nodes[fail].next.contains(ch)) {
                        fail = nodes[fail].fail;
                    }
                    
                    if (nodes[fail].next.contains(ch)) {
                        nodes[child].fail = nodes[fail].next[ch];
                    } else {
                        nodes[child].fail = 0;
                    }
                    
                    // 合并输出
                    nodes[child].output.append(nodes[nodes[child].fail].output);
                    
                    queue.enqueue(child);
                }
            }
        }
        
        qhash<int, qvector<int>> search(const qstring& text) {
            qhash<int, qvector<int>> results;
            int current = 0;
            
            for (int i = 0; i < text.length(); i++) {
                qchar ch = text[i];
                
                while (current != 0 && !nodes[current].next.contains(ch)) {
                    current = nodes[current].fail;
                }
                
                if (nodes[current].next.contains(ch)) {
                    current = nodes[current].next[ch];
                } else {
                    current = 0;
                }
                
                for (int patternid : nodes[current].output) {
                    results[patternid].append(i);
                }
            }
            
            return results;
        }
        
    private:
        qvector<node> nodes;
    };
};

// main.cpp
#include <qcoreapplication>
#include <qdebug>
#include "stringfinder.h"
#include "efficientstringsearcher.h"

int main(int argc, char *argv[])
{
    qcoreapplication a(argc, argv);
    
    qdebug() << "=== qstring 查找子串示例 ===";
    
    // 示例1: 基本查找
    {
        qdebug() << "\n1. 基本查找示例:";
        qstring text = "the quick brown fox jumps over the lazy dog.";
        
        qdebug() << "文本:" << text;
        qdebug() << "包含 'fox':" << text.contains("fox");
        qdebug() << "'fox' 位置:" << text.indexof("fox");
        qdebug() << "'the' 最后位置:" << text.lastindexof("the");
    }
    
    // 示例2: 使用stringfinder
    {
        qdebug() << "\n2. 使用stringfinder:";
        qstring text = "apple banana apple orange apple";
        
        qvector<int> positions = stringfinder::findall(text, "apple");
        qdebug() << "'apple' 所有位置:" << positions;
        
        int count = stringfinder::countoccurrences(text, "apple");
        qdebug() << "'apple' 出现次数:" << count;
        
        qstring highlighted = stringfinder::highlightall(text, "apple", "[", "]");
        qdebug() << "高亮显示:" << highlighted;
    }
    
    // 示例3: 正则表达式查找
    {
        qdebug() << "\n3. 正则表达式查找:";
        qstring text = "email: test@example.com, phone: 123-456-7890";
        
        qregularexpression emailregex(r"(\b\w+@\w+\.\w+\b)");
        qregularexpressionmatch match = emailregex.match(text);
        
        if (match.hasmatch()) {
            qdebug() << "找到邮箱:" << match.captured(0);
        }
        
        qregularexpression phoneregex(r"(\d{3}-\d{3}-\d{4})");
        match = phoneregex.match(text);
        
        if (match.hasmatch()) {
            qdebug() << "找到电话:" << match.captured(0);
        }
    }
    
    // 示例4: 高效算法比较
    {
        qdebug() << "\n4. 高效算法比较:";
        qstring text = qstring(10000, 'a') + "b" + qstring(10000, 'a');
        qstring pattern = "aaaab";
        
        // 普通查找
        auto start = std::chrono::high_resolution_clock::now();
        qvector<int> naivepositions = stringfinder::findall(text, pattern);
        auto end = std::chrono::high_resolution_clock::now();
        auto naivetime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        
        // kmp算法
        start = std::chrono::high_resolution_clock::now();
        qvector<int> kmppositions = efficientstringsearcher::kmpsearch(text, pattern);
        end = std::chrono::high_resolution_clock::now();
        auto kmptime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        
        // boyer-moore算法
        start = std::chrono::high_resolution_clock::now();
        qvector<int> bmpositions = efficientstringsearcher::boyermooresearch(text, pattern);
        end = std::chrono::high_resolution_clock::now();
        auto bmtime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        
        qdebug() << "朴素算法时间:" << naivetime << "微秒";
        qdebug() << "kmp算法时间:" << kmptime << "微秒";
        qdebug() << "boyer-moore算法时间:" << bmtime << "微秒";
        qdebug() << "找到的位置数量:" << naivepositions.size();
    }
    
    // 示例5: 多模式搜索
    {
        qdebug() << "\n5. 多模式搜索(aho-corasick):";
        
        efficientstringsearcher::ahocorasick ac;
        
        // 添加模式
        ac.addpattern("he", 0);
        ac.addpattern("she", 1);
        ac.addpattern("his", 2);
        ac.addpattern("hers", 3);
        
        ac.buildfailurelinks();
        
        qstring text = "ushers";
        auto results = ac.search(text);
        
        qdebug() << "在 '" << text << "' 中找到的模式:";
        for (auto it = results.begin(); it != results.end(); ++it) {
            qstring pattern;
            switch (it.key()) {
            case 0: pattern = "he"; break;
            case 1: pattern = "she"; break;
            case 2: pattern = "his"; break;
            case 3: pattern = "hers"; break;
            }
            
            qdebug() << "  模式 '" << pattern << "' 在位置:" << it.value();
        }
    }
    
    return 0;
}