字符串的暴力匹配和KMP算法

本文主要是介绍字符串的暴力匹配和KMP算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//字符串的暴力匹配---------------------------------------------------------------------
//创建一个结构体
typedef struct String
{
   char* data;
   int len;
}String;
//字符串初始化
String* InitString()
{
   String* s = (String*)malloc(sizeof(String));
   s->data = NULL;
   s->len = 0;
   return s;
}
//字符串赋值
void stringAssign(String* s, const char* data)
{
   //判断是否有值
   if (s->data)
   {
       free(s->data);
   }
   //计算data中字符的长度
   int len = 0;
   const char* tmp = data;
   while (*tmp)
   {
       len++;
       tmp++;
   }
   //如果字符串为空
   if (len == 0)
   {
       s->data = NULL;
       s->len = 0;
   }
   //字符串拷贝赋值
   else
   {
       tmp = data;
       s->len = len;
       //开辟字符串内存，多开一个用来保存 \0 字符串结束
       s->data = (char*)malloc(sizeof(char) * (len + 1));
       //拷贝
       for (int i = 0; i < len; i++, tmp++)
       {
           s->data[i] = *tmp;
       }
   }
}
//字符串的暴力匹配
void forceMatch(String* master, String* sub)
{
   //创建两个变量作为下标访问两个字符串
   int pm = 0;
   int ps = 0;
   //两个字符串都未遇到字符串结束标志时，执行循环比较
   while (pm < master->len && ps < sub->len)
   {
       //当master字符串中的字符与sub字符串首元素相同时，二者同时往后迭代比较
       if (master->data[pm] == sub->data[ps])
       {
           pm++;
           ps++;
       }
       //否则，从master中字符的下一个位置开始下一轮比较
       //即pm-ps+1的位置开始比较
       else
       {
           pm = pm - ps + 1;
           ps = 0;
       }
   }
   //当ps走完整个sub字符串，说明匹配上了
   if (ps == sub->len)
   {
       printf("force match success\n");
   }
   else
   {
       printf("force match false\n");
   }

}
//字符串打印
void printString(String* s)
{
   for (int i = 0; i < s->len; i++)
   {
       printf(i == 0 ? "%c" : "->%c ", s->data[i]);
   }
   printf("\n");
}

int main()
{
String* s = InitString();
String* s1 = InitString();

stringAssign(s, "hello");
stringAssign(s1, "ele");

printString(s);
printString(s1);

forceMatch(s, s1);

   return 0;
}
//字符串匹配的KMP算法------------------------------------------------------------------
//高效的模式匹配算法，不需要主串指针回溯，牺牲空间存储Next数组
// 更加智能的移动字符串，达到匹配效果
// next数组是：
// 当子串中字符与主串发生不匹配时，值对应索引的字符要移动到与主串不匹配的字符
// 对齐
//
// next数组算法：
// next的值=公共前后缀（相等字符个数） + 1，首元素为0，第二个元素为0+1
// 即相同字符个数0个，再+1
// 公共前后缀：abcd 前缀：a,ab,abc 后缀：d，cd，bcd
// 减少主串指针的移动，提高匹配效率
//创建一个结构体
typedef struct String
{
   char* data;
   int len;
}String;
//字符串初始化
String* InitString()
{
   String* s = (String*)malloc(sizeof(String));
   s->data = NULL;
   s->len = 0;
   return s;
}
//字符串赋值
void stringAssign(String* s, const char* data)
{
   //判断是否有值
   if (s->data)
   {
       free(s->data);
   }
   //计算data中字符的长度
   int len = 0;
   const char* tmp = data;
   while (*tmp)
   {
       len++;
       tmp++;
   }
   //如果字符串为空
   if (len == 0)
   {
       s->data = NULL;
       s->len = 0;
   }
   //字符串拷贝赋值
   else
   {
       tmp = data;
       s->len = len;
       //开辟字符串内存，多开一个用来保存 \0 字符串结束
       s->data = (char*)malloc(sizeof(char) * (len + 1));
       //拷贝
       for (int i = 0; i < len; i++, tmp++)
       {
           s->data[i] = *tmp;
       }
   }
}
//求出next数组-----------------
int* getNext(String* s)
{
   //给next数组开辟空间,与字符串元素个数相同
   int* next = (int*)malloc(sizeof(int) * s->len);
   int i = 0;//字符串的下标
   int j = -1;//next数组的公共前后缀的值
   //next数组首元素赋值，公共前后缀首元素的相同个数为-1
   next[i] = j;
   //首元素已赋值，访问下标次数-1
   while (i<s->len-1)
   {
       //当j == -1或者i下标所在字符前一个字符与j下标所在字符相同，二者同时往后迭代
       if (j == -1 || s->data[i] == s->data[j])
       {
           i++;
           j++;
           next[i] = j;
       }
       //否则，用i下标所在的元素与next[j]下标所在的元素进行比较，相同往后迭代
       // 或者直到j==-1,往后迭代
       else
       {
           j = next[j];
       }
   }
   return next;
}
//使用next数组，求解子串与主串匹配
void kmpMatch(String* master, String* sub,int* next)
{
   //创建两个变量作为下标访问两个字符串
   int pm = 0;
   int ps = 0;
   //两个字符串都未遇到字符串结束标志时，执行循环比较
   while (pm < master->len && ps < sub->len)
   {
       //当master字符串中的字符与sub字符串首元素相同时，二者同时往后迭代比较
       // 或者直到j==-1,往后迭代
       if (ps == -1 || master->data[pm] == sub->data[ps])
       {
           pm++;
           ps++;
       }
       //否则子串首元素移至主串pm下标所在位置，再次匹配
       else
       {
           ps = next[ps];
       }
   }
   //当ps走完整个sub字符串，说明匹配上了
   if (ps == sub->len)
   {
       printf("force match success\n");
   }
   else
   {
       printf("force match false\n");
   }
}
//打印next数组的值
void printNext(int* next, int len)
{
   for (int i = 0; i < len; i++)
   {
       printf(i == 0 ? "%d" : "->%d ", next[i]);
   }
   printf("\n");
}
//字符串打印
void printString(String* s)
{
   for (int i = 0; i < s->len; i++)
   {
       printf(i == 0 ? "%c" : "->%c ", s->data[i]);
   }
   printf("\n");
}