• 11.3-11.4kmp专题训练

    目录

    总结

    Number Sequence

    Oulipo

    剪花布条

    Cyclic Nacklace 

    Period

     Power Strings

    Seek the Name, Seek the Fame

    Blue Jeans

    Simpsons’ Hidden Talents

     Count the string

    总结

    题单链接传送门

    kmp算法，最核心的就是理解pmt数组，pmt数组前缀后缀相等的最大长度，那么可以理解为记录为上次匹配的位置,所以每次递归的长度是j-pmt[j-1]；其次就是pmt可以判断是否有循环节(n%(n−pmt[n-1])==0 && pmt[n-1]),这里的n-pmt[n-1]是最小的循环节，那么循环次数就是n/(n-pmt[n-1]).

    Number Sequence

    原题链接传送门

    kmp模板题，要注意的是这里是数字，不能让它们转化为字符串再去求(这里没仔细读题wa了很多发)，直接按数组去求就好了。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #define int long long
    7. using namespace std;
    8.  
    9. const int N = 1e6 + 9;
    10. int n, m;
    11. int pmt[N];
    12. int s[N], p[N];
    13.  
    14. signed main()
    15. {
    16.     ios::sync_with_stdio(false);
    17.     cin.tie(nullptr);
    18.     int t;
    19.     std::cin >> t;
    20.     while (t--)
    21.     {
    22.         int n, m;
    23.         cin >> n >> m;
    24.         for (int i = 0; i < n; i++) cin >> s[i];
    25.         for (int j = 0; j < m; j++) cin >> p[j];
    26.         for (int i = 1, j = 0; i < m; i++)
    27.         {
    28.             while (j && p[i] != p[j]) j = pmt[j - 1];
    29.             if (p[i] == p[j]) j++;
    30.             pmt[i] = j;
    31.         }
    32.         bool flag = 0;
    33.         for (int i = 0, j = 0; i < n; i++)
    34.         {
    35.             while (j && s[i] != p[j]) j = pmt[j - 1];
    36.             if (s[i] == p[j]) j++;
    37.             if (j == m){
    38.                 flag = true;
    39.                 cout << i - j + 2 << "\n";
    40.                 break;
    41.             }
    42.         }
    43.         if(!flag) cout << -1 << "\n";
    44.     }
    45.     return 0;
    46. }

    Oulipo

    原题链接传送门 

    模式串在匹配串中出现的次数，模板题。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #define int long long
    7. using namespace std;
    8.  
    9. const int N = 1e6 + 9;
    10. int pmt[N];
    11.  
    12. void get_pmt(const string& p) {
    13.     for(int i = 1, j = 0; i < p.size(); i++)
    14.     {
    15.         while(j && p[i] != p[j]) j = pmt[j - 1];
    16.         if(p[i] == p[j]) j ++;
    17.         pmt[i] = j;
    18.     }
    19. }
    20.  
    21. int kmp(const string& s, const string& p) {
    22.     int ans = 0;
    23.     for(int i = 0, j = 0; i < s.size(); i++)
    24.     {
    25.         while(j && s[i] != p[j]) j = pmt[j - 1];
    26.         if(s[i] == p[j]) j ++;
    27.         if(j == p.size()){
    28.             ans++;
    29.             j = pmt[j - 1];
    30.         }
    31.     }
    32.     return ans;
    33. }
    34.  
    35. signed main()
    36. {
    37.     ios::sync_with_stdio(false);
    38.     cin.tie(nullptr);
    39.     int t;
    40.     std::cin >> t;
    41.     while(t--){  
    42.         string p, s;
    43.         cin >> p >> s;
    44.         get_pmt(p);
    45.         cout << kmp(s, p) << endl;
    46.     }
    47.     return 0;
    48. }

    剪花布条

    原题链接传送门 

    一个字符串能分成相同的几段，这里要注意由于不能有重叠部分所以在递归匹配时重新从0开始即可。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. const int N = 1e6 + 9;
    9. int pmt[N];
    10.  
    11. void get_pmt(const string& s) { 
    12.     for(int i = 1, j = 0; i < s.size(); i++)
    13.     {
    14.         while(j && s[i] != s[j]) j = pmt[j - 1];
    15.         if(s[i] == s[j]) j ++;
    16.         pmt[i] = j;
    17.     }
    18. }
    19.  
    20. int kmp(const string& s, const string& p) {
    21.     int ans = 0;
    22.     for(int i = 0, j = 0; i < s.size(); i++)
    23.     {
    24.         while(j && s[i] != p[j]) j = pmt[j - 1];
    25.         if(s[i] == p[j]) j ++;
    26.         if(j == p.size())
    27.         {
    28.             ans++;
    29.             // j = pmt[j - 1];
    30.             j = 0;
    31.         }
    32.     }
    33.     return ans;
    34. }
    35.  
    36. int main()
    37. {
    38.     ios::sync_with_stdio(false);
    39.     cin.tie(0);
    40.     string s, p;
    41.     while(cin >> s)
    42.     {
    43.         if(s == "#") break;
    44.         cin >> p;
    45.         get_pmt(s);
    46.         int m = p.size();
    47.         cout << kmp(s, p) << endl;
    48.     }
    49.     return 0;
    50. }

    Cyclic Nacklace 

    原题链接传送门 

    题意：一个字符串最少加多少个字符能使字符串变成周期循环.

    思路：最小循环节为n-pmt[n-1],所以加的最小长度就是n-pmt[n-1]-pmt[n-1]%(n-pmt[n-1]).

    1. #include 
    2. using namespace std;
    3. const int N = 1e6 + 9;
    4. int n, m;
    5. int pmt[N];
    6. char s[N];
    7.  
    8. signed main()
    9. {
    10.     int t;
    11.     scanf("%d",&t);
    12.     while(t--) {
    13.         scanf("%s",s);
    14.         int n = strlen(s);
    15.         for(int i = 1, j = 0; i < n; i++){
    16.             while(j && s[i] != s[j]) j = pmt[j - 1];
    17.             if(s[i] == s[j]) j ++;
    18.             pmt[i] = j;
    19.         }
    20.         int l = pmt[n - 1], r = n - l;
    21.         if(l && l % r == 0) cout << 0 << endl;
    22.         else cout << r - l % r << endl;
    23.     }
    24.     return 0;
    25. }

    Period

    原题链接传送门 

    一个字符串,问在所有的[0, i]区间是否有完整的循环节，同样利用了pmt对循环节的求解。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7.  
    8. const int N = 1e6 + 9;
    9. int n, m;
    10. int pmt[N];
    11.  
    12. signed main()
    13. {
    14.     ios::sync_with_stdio(false);
    15.     cin.tie(nullptr);
    16.     int n;
    17.     int test = 0;
    18.     while(cin >> n && n != 0) {
    19.         string s;
    20.         cin >> s;
    21.         for(int i = 1, j = 0; i < n; i++){
    22.             while(j && s[i] != s[j]) j = pmt[j - 1];
    23.             if(s[i] == s[j]) j ++;
    24.             pmt[i] = j;
    25.         }
    26.         cout << "Test case #" << ++test << "\n";
    27.         for(int i = 0; i < n; i++){
    28.             int j = i + 1;
    29.             int k = j - pmt[i];
    30.             if(j % k == 0 && pmt[i]) 
    31.                 cout << j << " " <<  j / k << "\n";
    32.         }
    33.         cout << "\n";
    34.     }
    35.     return 0;
    36. }

     Power Strings

    原题链接传送门

    题意：假设s可以由t重复k次拼成，即s=tttt……tt，我们称为s=t^k，k是s的幂次。先给定一个字符串s，求最大的幂次n使得存在t满足s=t^n。先看看是不是周期循环，否输出1是输出循环次数即可。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int N = 1e6 + 9;
    8. int pmt[N];
    9.  
    10. void get_pmt(const string& s) { 
    11.     for(int i = 1, j = 0; i < s.size(); i++)
    12.     {
    13.         while(j && s[i] != s[j]) j = pmt[j - 1];
    14.         if(s[i] == s[j]) j ++;
    15.         pmt[i] = j;
    16.     }
    17. }
    18.  
    19. int main()
    20. {
    21.     ios::sync_with_stdio(false);
    22.     cin.tie(0);
    23.     string s;
    24.     while(cin >> s)
    25.     {
    26.         if(s == ".") break;
    27.         get_pmt(s);
    28.         int n = s.size();
    29.         int m = n - 1;
    30.         if(n % (n - pmt[m])) std::cout << "1\n";
    31.         else std::cout << n / (n - pmt[m]) << "\n";
    32.     }
    33.     return 0;
    34. }

    Seek the Name, Seek the Fame

    原题链接传送门

    题意：在每个字符串中求出所有既是前缀又是后缀的子串长度。

    思路：pmt表示前缀与后缀相等的最大长度，递归pmt即可。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8.  
    9. const int N = 1e6 + 9;
    10. int n, m;
    11. int pmt[N], ans[N];
    12. char s[N];
    13.  
    14. signed main()
    15. {
    16.     while(~scanf("%s",s)) {
    17.         int n = strlen(s);
    18.         for(int i = 1, j = 0; i < n; i++){
    19.             while(j && s[i] != s[j]) j = pmt[j - 1];
    20.             if(s[i] == s[j]) j ++;
    21.             pmt[i] = j;
    22.         }
    23.         int cnt = 0;
    24.         for(int j = n; j; j = pmt[j - 1]) ans[++cnt] = j;
    25.         for(int i = cnt; i; i--) cout << ans[i] << " \n"[i == 1];
    26.     }
    27.     return 0;
    28. }

    Blue Jeans

    原题链接传送门

    多个字符串的公共子序列，水题暴力枚举即可。

    1. #include 
    2. #include 
    3. #include 
    4. signed main(){
    5.     int T, n;
    6.     std::cin >> T;
    7.     while (T--){
    8.         std::cin >> n;
    9.         std::string s, t;
    10.         std::vector str;
    11.         std::set ans;
    12.         for (int i = 0; i < n; i++)
    13.             std::cin >> s, str.push_back(s);
    14.         bool f, fy = 0;
    15.         s = str[0];
    16.         for (int i = 60; i >= 3; i--){
    17.             for (int j = 0; i + j <= 60; j++){
    18.                 f = 1, t = s.substr(j, i);
    19.                 for (int k = 1; k < str.size(); k++)
    20.                     if ((int)str[k].find(t) == -1){
    21.                         f = 0;
    22.                         break;
    23.                     }
    24.                 if (f) ans.insert(t);
    25.             }
    26.             if (!ans.empty()){
    27.                 fy = 1;
    28.                 break;
    29.             }
    30.         }
    31.         std::cout << ((fy) ? (*(ans.begin())) : "no significant commonalities");
    32.         std::cout << "\n";
    33.     }
    34.     return 0;
    35. }

    Simpsons’ Hidden Talents

    原题链接传送门

    题意：两个字符串s，t，输出同时作为s前缀和t后缀的最长字符串，然后输出该字符串的长度

    思路：根据题意，我们可以选择将两个字符拼在一起，最后找到长度不大于s或t的任意一个既是前缀又是后缀的字符串即可。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #define int long long
    9. using namespace std;
    10.  
    11. const int mod = 10007;
    12. const int N = 1e6 + 9;
    13. int n, m;
    14. int pmt[N];
    15.  
    16. void get_pmt(const string& s) { 
    17.     for(int i = 1, j = 0; i < s.size(); i++)
    18.     {
    19.         while(j && s[i] != s[j]) j = pmt[j - 1];
    20.         if(s[i] == s[j]) j ++;
    21.         pmt[i] = j;
    22.     }
    23. }
    24.  
    25. signed main()
    26. {
    27.     ios::sync_with_stdio(false);
    28.     cin.tie(nullptr);
    29.     string s, p;
    30.     while(cin >> s >> p) {
    31.         int lens = s.size(), lenp = p.size();
    32.         s = s + p;
    33.         get_pmt(s);
    34.         n = s.size();
    35.         int ans = pmt[n - 1];
    36.         while(ans > lens || ans > lenp) ans = pmt[ans];
    37.         if(ans==0) {cout<<0<continue;}
    38.         cout << s.substr(0, ans) << " " << ans << endl;
    39.     }
    40.     return 0;
    41. }
    42.

     Count the string

    原题链接传送门

    题意：给定一个字符串s，求s的每个前缀在此字符串中出现的次数，然后对次数求和，然后再对10007取模，就是要输出的答案。

    思路：主要考察对pmt数组的理解，每个前缀至少出现一次，如果i匹配失败，会回到pmt[i-1],所以当前的字符串包含pmt[i-1]包含的前缀和它本身。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #define int long long
    9. using namespace std;
    10.  
    11. const int mod = 10007;
    12. const int N = 1e6 + 9;
    13. int n, m;
    14. int pmt[N];
    15. string s;
    16.  
    17. void get_pmt(const string& s) { 
    18.     for(int i = 1, j = 0; i < s.size(); i++)
    19.     {
    20.         while(j && s[i] != s[j]) j = pmt[j - 1];
    21.         if(s[i] == s[j]) j ++;
    22.         pmt[i] = j;
    23.     }
    24. }
    25.  
    26. signed main()
    27. {
    28.     ios::sync_with_stdio(false);
    29.     cin.tie(nullptr);
    30.     int t;
    31.     cin >> t;
    32.     while(t--) {
    33.         cin >> n >> s;
    34.         get_pmt(s);
    35.         int ans = 0;
    36.         for(int i = 0; i < n; i++) if(pmt[i]) ans = (ans + 1) % mod;
    37.         cout << (ans + n) % mod << "\n";
    38.     }
    39.     return 0;
    40. }

      2022/11/5 0:45补11.3-11.4

  • 相关阅读:
    RK3568笔记分享之“如何挂载SPI FRAM铁电存储芯片”——飞凌嵌入式
    C++ 类和对象(B)
    什么耳机音质最好又不伤耳朵，什么耳机好用耳朵不疼
    【TypeScript】函数类型：返回值类型和参数类型到底如何定义？
    操作系统绪论习题
    R语言进行数据分组聚合统计变换（Aggregating transforms）、计算dataframe数据的分组独特值的个数（distinct）
    Redis 分布式锁
    上周热点回顾（4.1-4.7）
    Element-UI+Vue实现开发权限
    minikube 快速使用入门 - pod - 外传
  • 原文地址：https://blog.csdn.net/weixin_62802134/article/details/127698252