发布时间：2024-01-25

KMP模板

P3375【模板】KMP

int nxt[N];
string s,p;
void solve(){
    cin>>s>>p;
    int ls=s.size(),lp=p.size();    
    s=" "+s;
    p=" "+p;
    for(int i=2,j=0;i<=lp;i++){
        while(j&&p[i]!=p[j+1])j=nxt[j];
        if(p[i]==p[j+1])j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=ls;i++){
        while(j&&s[i]!=p[j+1])j=nxt[j];
        if(s[i]==p[j+1])j++;
        if(j==lp){
            cout<<i-lp+1<<"\n";
            j=nxt[j];
        }
    }
    for(int i=1;i<=lp;i++)cout<<nxt[i]<<" ";
}

P4391无线传输

求最小循环串,即n-nxt[n]

//最小循环串：n-ne[n];
int ne[N];
string s,p;
void solve(){
    cin>>s>>p;
    int ls=s.size(),lp=p.size();    
    s=" "+s;
    p=" "+p;
    for(int i=2,j=0;i<=lp;i++){
        while(j&&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=ls;i++){
        while(j&&s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==lp){
            cout<<i-lp+1<<"\n";
            j=ne[j];
        }
    }
    for(int i=1;i<=lp;i++)cout<<ne[i]<<" ";
}

leetcode3213 最小代价构造字符串

题意：

给定一个字符串数组，每一个字符串都有一个代价
问组成target字符串的最小代价是多少

思路1：字符串哈希

• 首先考虑暴力，得到dp方程： $f_i=f_j+cost(i,j) ,j<i$
• 暴力转移为 $O(n)$
• 仔细考虑，字符串数组总长为 $L=5e4$ ,那么不同的长度最多为 $O( \sqrt n)$ 个，$1+2+3....=L$
• 因此哈希转移的时间复杂度为$O(n \sqrt L)$

class Solution {
public:
const unsigned long long B=131;
typedef unsigned long long ULL;
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        unordered_map<unsigned long long,int> mp;
        int n=target.size();
        vector<ULL> h(n+1),pw(n+1);
        pw[0]=1;        
        for(int i=0;i<n;i++)h[i+1]=h[i]*B+target[i],pw[i+1]=pw[i]*B;
        vector<int> len;
        for(int i=0;i<words.size();i++){
            len.push_back(words[i].length());
            ULL cnt=0;
            for(auto c:words[i])cnt=cnt*B+c;
            if(mp.count(cnt))mp[cnt]=min(mp[cnt],costs[i]);
            else mp[cnt]=costs[i];
        }
        sort(len.begin(),len.end());
        len.erase(unique(len.begin(),len.end()),len.end());
        vector<int> f(n+1,1e9);
        auto getHash=[&](int l,int r){
            return h[r]-h[l-1]*pw[r-l+1];
        };
        f[0]=0;
        for(int i=1;i<=n;i++){
            for(auto it:len){
                if(i-it>=0){
                    auto x=getHash(i-it+1,i);
                    if(mp.count(x)){
                        f[i]=min(f[i-it]+mp[x],f[i]);
                    }
                }
            }
        }
        return f[n]==1e9?-1:f[n];
    }
};

思路2：AC自动机

• 建立ac自动机并查询即可
• 需要注意的点：查询时如果一直往前跳回发生复杂度退化，因此应该记录上一个存在的点是哪，保证跳 $O( \sqrt L )$ 次

class Solution {
public:
    #define N 50010
    int tr[N][26],cnt[N],ne[N],len[N],lst[N];
    int idx=0;
    void insert(string &s,int cost){
        int p=0;
        for(int i=0;i<s.size();i++){
            int v=s[i]-'a';
            if(!tr[p][v])tr[p][v]=++idx;
            p=tr[p][v];
        }
        if(cnt[p]>cost){
            cnt[p]=cost;
            len[p]=s.size();
        }
    }
    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(tr[0][i])q.push(tr[0][i]);
        }
        while(!q.empty()){
            auto u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                int &p=tr[u][i];
                if(!p)p=tr[ne[u]][i];
                else{
                    ne[p]=tr[ne[u]][i];
                    if(cnt[ne[p]]!=1e9)lst[p]=ne[p];
                    else lst[p]=lst[ne[p]];
                    q.push(tr[u][i]);
                }
            }
        }
    }
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        for(int i=0;i<N;i++){
            cnt[i]=1e9;
            ne[i]=len[i]=lst[i]=0;
            for(int j=0;j<26;j++)tr[i][j]=0;
        }
        for(int i=0;i<words.size();i++){
            insert(words[i],costs[i]);
        }
        int n=target.size();     
        vector<int> f(n+1,1e9);
        f[0]=0;
        build();
        for(int i=1,j=0;i<=n;i++){
            int v=target[i-1]-'a';
            j=tr[j][v];
            int p=j;
            while(p){
                if(cnt[p]!=1e9)f[i]=min(f[i],f[i-len[p]]+cnt[p]);
                p=lst[p];
            }
        }
        return f[n]==1e9?-1:f[n];
    }
};