本文主要是介绍2982. 找出出现至少三次的最长特殊子字符串 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
字典树思路
用字典树搞一下就好了，比如aaaaa ： a存5次 aa 4次以此类推～
字典树板子复习：P8306 【模板】字典树
这里这个清空方式 很好 因为很多时候memset T
#include<iostream>
#include<cstring>
using namespace std;const int N = 3e6+10;
int n,m;
string s;
int tire[N][70],cnt[N],idx;void insert(){int p = 0;for(auto &t:s){int u;if(t>='a'&&t<='z')u = t-'a';else if(t>='A'&&t<='Z')u = t-'A'+ 27;else u = t -'0'+54;if(!tire[p][u]) tire[p][u]=++idx;p = tire[p][u]; cnt[p]++;}
}int query(){int p=0;for(auto &t:s){int u;if(t>='a'&&t<='z')u = t-'a';else if(t>='A'&&t<='Z')u = t-'A'+ 27;else u = t -'0'+54;if(!tire[p][u]) return 0;p = tire[p][u];}return cnt[p];
}void solve()
{cin>>n>>m;for(int i=0;i<=idx;i++)for(int j=0;j<=65;j++)tire[i][j] = 0;for(int i=0;i<=idx;i++)cnt[i] = 0;idx = 0;while(n--){cin>>s;insert();}while(m--){cin>>s;cout<<query()<<"\n";}
}int main()
{int _;cin>>_;while(_--)solve();
}本题代码;
const int N = 5e5+10;
int tr[N][27],cnt[N],idx;
class Solution {
public:string str;void insert(){int ts = str.size();int p = 0;for(auto &t:str){int u = t - 'a';if(!tr[p][u])tr[p][u] = ++idx;p = tr[p][u];cnt[p]+=ts--;}}int find(char c){ int p = 0;int t = 0;int u = c-'a';while(cnt[tr[p][u]]>=3){t++;p = tr[p][u];}return t;}int maximumLength(string s) {for(int i=0;i<=idx;i++)for(int j=0;j<=26;j++)tr[i][j] = 0;for(int i=0;i<=idx;i++)cnt[i] = 0;idx = 0;char c = s[0];int t = 1;for(int i=1;i<s.size();i++){if(s[i]!=c){str = "";while(t--)str+=c;insert();cout<<str<<"\n";c = s[i];t = 1;}else t++;}str = "";while(t--)str+=c;insert();cout<<str<<"\n";int ans = 0;for(char i='a';i<='z';i++) ans = max(ans,find(i));if(ans)return ans;return -1;}
};这篇关于2982. 找出出现至少三次的最长特殊子字符串 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
