【编程之美】字符串移位包含的问题

妖狐艹你老母 2022-04-24 15:28 199阅读 0赞

问题描述：

给定两个字符串s1和s2，要求判定s2是否能被s1循环移位（rotate）得到的字符串包含。例如，给定字符串s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD返回false。

分析：

从问题的描述来看，最直接的方式就是对字符串s1进行循环移位，再判断s1是否包含s2. 关于字符串匹配可以使用KMP算法，这不是本问题的中心，因此我们使用库函数strstr来匹配。char\* strstr(char \*haystack, char \*needle);如果needle为haystack的子串则返回出现的位置，否则返回NULL。

解法一：

![复制代码][copycode.gif]

#include <stdio.h>
     #include <stdlib.h>
     #include <string.h>
    
    int main(void)
    {
         char a[] = "AABCD";
         char b[] = "CDAA";
     
         int i, j, res;
         char tmp;
         int len = strlen(a);
     
         for(i = 0; i < len; i++)
         {
             tmp = a[0];
             for(j = 0; j < len-1; j++)
            {
                 a[j] = a[j+1];
              }
             a[len-1] = tmp;
     
             if(strstr(a,b))
              {
                 printf("OK");
                 return 0;
             }
         }
         printf("NOT OK");
     
         return 0;
    }

![复制代码][copycode.gif]

这样做的时间代价是很高的，如果匹配不到，则总共进行了n-1次循环移位和匹配。

那么，有没有其他办法可以不用穷举s1每次循环移位的结果呢？

我们先来观察以下s1循环移位后到底是什么样子？

“AABCD"->"ABCDA"->"BCDAA"->"CDAAB"->"DAABC"

s2=“CDAA”

从上面可以看出来，解法1有很多重复的匹配。例如“CDAA”在匹配到“CD”以后需要循环移位一次重新匹配“CDA”然后“CDAA”，所以主要时间浪费在了循环移位s1上。那么一个比较简单的想法就是如果能让s2=“CDAA”直接去匹配像“CDAAB”这样的串就可以了。

如果仅仅是把s1的前面每一位“接”到其末尾，那么“AABCDAABCD”就可以对s2进行直接匹配。事实上，如果length(s2)<=length(s1)的情况下，如果s1s1包含s2，那么其循环移位的结果也是包含s2的。

解法二：

![复制代码][copycode.gif]

#include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(void)
    {
      char a[] = "AABCD";
      char b[] = "CDAA";
      char c[] = "AABCDAABCD"
      if(strstr(c,b)!=NULL)
         printf("OK");
      else
         printf("NOT OK");
       return 0;   
    }

![复制代码][copycode.gif]

解法二用空间换取了大量的计算时间。只需要一次匹配即可得到结果。

[copycode.gif]: /images/20220212/e691a9c60b274052b3c106fc4859dea6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串移位包含问题

include <stdio.h> include <stdlib.h> include <string.h> int main(int arg

小灰灰/ 2022年12月11日 13:50/ 0 赞/ 120 阅读

相关字符串是否包含问题

题目描述假设这有两个分别由字母组成的字符串A另外字符串B，字符串B的字母数较字符串A少一些。什么方法能最快地查出字符串B所有字母是不是都在字符串A里？也就是说判断字符串

柔光的暖阳◎/ 2022年08月27日 05:50/ 0 赞/ 255 阅读

相关字符串移位包含的问题——解题笔记

字符串移位包含的问题——解题笔记题目描述：给定两个字符串s1和s2，要求判定s2时候能够被s1做循环移位（rotate）得到的字符串包含。例如，给定s1=AAB

墨蓝/ 2022年08月06日 17:10/ 0 赞/ 159 阅读

相关编程之美-字符串移位包含的问题

第三章　3.1　字符串移位包含的问题问题详细描述: 给定两个字符串s1和s2，要求判断s2是否能够被s1做循环移位得到的字符串包含。输入输出示例：给定s1

ゝ一世哀愁。/ 2022年08月04日 12:48/ 0 赞/ 170 阅读

相关字符串移位包含的问题

问题：给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。例如，S1=AABCD和s2=CDAA，返回true；给定s1=ABC

清疚/ 2022年07月18日 01:12/ 0 赞/ 153 阅读

相关 java字符串包含问题

/ 用于判断用逗号分隔的字符串测试第一个字符串是否包含第二个字符串的内容若不包含则返回第一个不包含的内容

素颜马尾好姑娘i/ 2022年06月13日 01:22/ 0 赞/ 254 阅读

相关【算法】字符串循环移位后是否包含

问题 > 给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。 > 例如，s1=AABCD和s2=CDAA，返回tru

偏执的太偏执、/ 2022年06月02日 02:43/ 0 赞/ 204 阅读

相关计算字符串的相似度--编程之美3.3

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：　　1.修改一个字符（如

清疚/ 2022年05月24日 12:08/ 0 赞/ 221 阅读

相关字符串移位包含问题研究

问题：给定两个字符串s1和s2，要求判定s2是否能够通过s1做循环移位得到字符串包含，例如s1=AABCD，s2=CDAA，则返回true，如果s1=ABCD，s2=ACBD，

痛定思痛。/ 2022年05月15日 01:35/ 0 赞/ 214 阅读

相关【编程之美】字符串移位包含的问题

问题描述：给定两个字符串s1和s2，要求判定s2是否能被s1循环移位（rotate）得到的字符串包含。例如，给定字符串s1=AABCD和s2=CDAA，返回true；给定s

妖狐艹你老母/ 2022年04月24日 15:28/ 0 赞/ 200 阅读