使用C语言解决字符串匹配问题的方法

最常想到的方法是使用KMP字符串匹配算法:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int get_nextval(char *pattern, int next[])
{
  //get the next value of the pattern
  int i = 0, j = -1;
  next[0] = -1;
  int patlen = strlen(pattern);
  while ( i < patlen - 1){
    if ( j == -1 || pattern[i] == pattern[j]){
      ++i;
      ++j;
      if (pattern[i] != pattern[j])
        next[i] = j;
      else
        next[i] = next[j];
    }
    else
      j = next[j];
    }

  return(0);
}

int kmpindex(char *target, char *pattern, int pos)
{
  int tari = pos, pati = 0;
  int tarlen = strlen(target), patlen = strlen(pattern);
  int *next = (int *)malloc(patlen * sizeof(int));
  get_nextval(pattern, next);
  while ( tari < tarlen && pati < patlen ){
    if (pati == -1 ||target[tari] == pattern[pati]){
      ++tari;
      ++pati;
      }else{
        pati = next[pati];
      }
  }
if(next != NULL) free(next);
next = NULL;
if (pati == patlen)
  return tari - pati;
else
  return -1;
}

int main()
{
  char target[50], pattern[50];
  printf("imput the target:\n" );
  scanf("%s",target);
  printf("imput the pattern:\n" );
  scanf("%s",pattern);
  int ans = kmpindex(target,pattern,0);
  if (ans == -1)
    printf("error\n");
  else
    printf("index:%d\n",ans);
  return 0;
}

练习题
    题目描述: 
        读入数据string[ ],然后读入一个短字符串。要求查找string[ ]中和短字符串的所有匹配,输出行号、匹配字符串。匹配时不区分大小写,并且可以有一个用中括号表示的模式匹配。如“aa[123]bb”,就是说aa1bb、aa2bb、aa3bb都算匹配。 
    输入: 
    输入有多组数据。 
    每组数据第一行输入n(1<=n<=1000),从第二行开始输入n个字符串(不含空格),接下来输入一个匹配字符串。 
    输出: 
    输出匹配到的字符串的行号和该字符串(匹配时不区分大小写)。 
    样例输入: 
    4 
    Aab 
    a2B 
    ab 
    ABB 
    a[a2b]b 
    样例输出: 
    1 Aab 
    2 a2B 
    4 ABB

ac代码

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h> 

  #define MAX 1001
  #define LEN 101 

  struct str
  {
    char name[101];
  }; 

  int main()
  {
    struct str strs[MAX];
    struct str t[LEN];
    int i, n, len, j, k, left, right, count, flag;
    char text[LEN], newtext[LEN]; 

    while (scanf("%d", &n) != EOF) {
      // 接收数据
      getchar();
      for (i = 0; i < n; i ++) {
        scanf("%s", strs[i].name);
      } 

      // 接收文本串
      getchar();
      gets(text);
      len = strlen(text); 

      for (i = left = right = 0; i < len; i ++) {
        if (text[i] == '[') {
          left = i;
        } else if (text[i] == ']') {
          right = i;
          break;
        }
      }
      count = right - left - 1; 

      if (count <= 0) {  // 没有正则匹配
        for (i = j = 0; i < len; i ++) {
          if (text[i] != '[' && text[i] != ']') {
            newtext[j ++] = text[i];
          }
        }
        newtext[j] = '\0';
        for (i = 0; i < n; i ++) {
          if (strcasecmp(strs[i].name, newtext) == 0) {
            printf("%d %s\n", i + 1, strs[i].name);
          }
        }
      }else { // 需要正则匹配
        for (j = 1, k = 0; j <= count; j ++, k ++) { // 构建文本数组
          memset(t[k].name, '\0', sizeof(t[k].name));
          for (i = 0; i < left; i ++) {
            t[k].name[i] = text[i];
          }
          t[k].name[i] = text[left + j];
          strcat(t[k].name, text + right + 1);
        }   

        // 正则匹配
        for (i = 0; i < n; i ++) {
          for (j = flag = 0; j < count; j ++) {
            if (strcasecmp(strs[i].name, t[j].name) == 0) {
              flag = 1;
              break;
            }
          }
          if (flag) {
            printf("%d %s\n", i + 1, strs[i].name);
          }
        }
      } 

    } 

    return 0;
  }

/**************************************************************
        Problem: 1165
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:0 ms
        Memory:948 kb
    ****************************************************************/

(0)

相关推荐

  • 一些C语言中字符串的算法问题解决实例小结

    字符串问题是面试中经常出现的问题,这类问题有很多,难以不一.下面是几道字符串的题目,网上都能找到解答,自己实现了一下,供网友参考.感觉算法重要的是要有正确的思路,实现起来不是问题.自己一定要多思考,这样收获可能会更多一点.         问题1:找两个字符串的最长公共子串.         具体描述,如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求

  • C语言之字符串模糊查询方法的实现

    字符串模糊查询,主要是输入不完全的信息进行查找,即每次查找的是待查询的内容中是否含有输入的内容,如果有,则表示找到了.下面详细的介绍下模糊查询的实现方法,代码如下: #include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, const char * argv[]) { char str[] = "hello welcome to china\0"; //

  • C语言字符串大小比较

    C语言字符串大小比较 #include <stdio.h> #include <string.h> int fun(char *a,char *b) { int i = 0,j = 0; while(a[i]&&b[j]) { if(a[i]-b[j]>0) return 1; else if(a[i]-b[j]<0) return -1; i++,j++; } if(strlen(a)==i&&strlen(b)==j) return

  • C语言字符串快速压缩算法代码

    通过键盘输入一串小写字母(a~z)组成的字符串. 请编写一个字符串压缩程序,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串. 压缩规则: 1.仅压缩连续重复出现的字符.比如字符串"abcbc"由于无连续重复字符,压缩后的字符串还是"abcbc". 2.压缩字段的格式为"字符重复的次数+字符".例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz". 示例 输入:"cccddec

  • 与ASCII码相关的C语言字符串操作函数

    C语言toascii()函数:将字符转换成对应的ASCII码 头文件: #include <ctype.h> 定义函数: int toascii(int c); 函数说明:toascii()会将参数c 转换成7 位的unsigned char 值,第八位则会被清除,此字符即会被转成ASCII码字符. 返回值:将转换成功的ASCII 码字符值返回. 范例:将int 型a 转换成ASSII 码字符. #include <stdlib.h> main(){ int a = 217; ch

  • C语言左旋转字符串与翻转字符串中单词顺序的方法

    左旋转字符串 题目: 定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部. 如把字符串 abcdef  左旋转 2  位得到字符串 cdefab.请实现字符串左旋转的函数. 要求时间对长度为 n  的字符串操作的复杂度为 O(n),辅助内存为 O(1). 分析: 网上看到解法很多种,就不详细说明了. 我采用的是数组不对称的交换时间复杂度应该是O(n). 代码实现(GCC编译通过): #include "stdio.h" #include "stdlib.h&q

  • 字符串的组合算法问题的C语言实现攻略

    基本字符串组合问题 题目:输入一个字符串,输出该字符串中字符的所有组合.举个例子,如果输入abc,它的组合有a.b.c.ab.ac.bc.abc. 上面我们详细讨论了如何用递归的思路求字符串的排列.同样,本题也可以用递归的思路来求字符串的组合. 假设我们想在长度为n的字符串中求m个字符的组合.我们先从头扫描字符串的第一个字符.针对第一个字符,我们有两种选择:第一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符:第二是不把这个字符放到组合中去,接下来我们需要在剩下的n

  • C语言中一些将字符串转换为数字的函数小结

    C语言atoi()函数:将字符串转换成int(整数) 头文件: #include <stdlib.h> atoi() 函数用来将字符串转换成整数(int),其原型为: int atoi (const char * str); [函数说明]atoi() 函数会扫描参数 str 字符串,跳过前面的空白字符(例如空格,tab缩进等,可以通过 isspace() 函数来检测),直到遇上数字或正负符号才开始做转换,而再遇到非数字或字符串结束时('\0')才结束转换,并将结果返回. [返回值]返回转换后的

  • 使用C语言提取子字符串及判断对称子字符串最大长度

    先来看一个使用C语言从字符串中提取子字符串的基本方法总结: #include <stdio.h> /*处理中文字符*/ /*遍历字符串,非ASCII字符读取2个字节,ASCII读取一个字节,获取字符串长度*/ int StrLenU(const char* string) { int len = 0 ; const char* p = string; while(*p++ != '\0') { if(*p > 0x80 || *p < 0) { p++; } len++; } re

  • C语言中压缩字符串的简单算法小结

    应用中,经常需要将字符串压缩成一个整数,即字符串散列.比如下面这些问题: (1)搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节.请找出最热门的10个检索串. (2)有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M.返回频数最高的100个词. (3)有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复.要求你按照query的频度排序. (4)给定a.b两个文件

随机推荐