2016 UESTC Training for Search Algorithm & String I – 谭爷剪花布条 KMP

  Source

2016 UESTC Training for Search Algorithm & String

  My Solution

KMP 套版题

与自己收藏的模版唯一不同的是这里是子串不能重叠的，恰好自己的模版是返回一个vector存储着相应

子串的起始下标。

这样sort一下，然后开始一个一个访问，

如果前一个的起点为Ind + sz <= *iter 则记录进去，并维护Ind

如果Ind + sz > *iter, 则忽略当前这个匹配的子串

复杂度O(M + N) //M, N分别为T串和P串的长度

#include 
#include 
#include 
using namespace std;

void find_substring(const string& pattern, const string& text, vector& ans)
{
    int n = pattern.size();
    vector nxt(n+1, 0);
    for(int i = 1, j = 0; i < n; i++){ j = i; while(j > 0){
            j = nxt[j];
            if(pattern[j] == pattern[i]){
                nxt[i + 1] = j + 1;
                break;
            }
        }
    }

    int /*tot = 0,*/ m = text.size();
    for(int i = 0, j = 0; i < m; i++){
        if(j < n && text[i] == pattern[j]){ j++; } else{ while(j > 0){
                j = nxt[j];
                if(text[i] == pattern[j]){
                    j++;
                    break;
                }
            }
        }
        if(j == n){
            ans.push_back(i - n + 1);
        }
    }
}
//!Wrong Answer on test 33
//!能从花布条中剪出的最多小饰条个数，如果一块都没有，那就输出0  应该是有些地方子串有交叉了
//!如
//!ababababa
//!aba
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string P, T;
    vector ans;
    int tot = 0, sz , Ind;                           //P, 还没有输入呢， .size()  有什么用呀 cout<<sz<<endl; cin>>T>>P;
    sz = P.size();
    find_substring(P, T, ans);
    for(auto iter = ans.begin(); iter != ans.end(); iter++){
        //cout<<*iter<<" ";
        if(iter == ans.begin()) {tot++; Ind = *iter;}
        else{
            if(Ind + sz <= *iter){tot++; Ind = *iter;}
        }

    }
    cout<<tot;
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx