当前位置： 首页 > news >正文

青海网网站建设搜索引擎seo关键词优化

news 2025/7/21 23:40:42
青海网网站建设,搜索引擎seo关键词优化,微信朋友圈推广软文,重庆黄埔建设集团网站一、题目给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。示例 1：输入：haystack …

一、题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"

输出：0

解释："sad" 在下标 0 和 6 处匹配。

第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"

输出：-1

解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

  • 1 <= haystack.length, needle.length <= 10**4

  • haystack 和 needle 仅由小写英文字符组成

二、解题思路

这里可以用两种方法进行解题，一种是BF算法（暴力搜索算法），算法时间复杂度为O(n*m)，另一种是KMP算法（BF算法改进），算法时间复杂度为O(n+m)。这里我们用KMP算法进行解题，最好结合着《三、函数介绍》来看。

在进行字符串匹配之前，我们需要算出模式串的前缀表，也就是算出模式串从第一个字符到倒数第二字符的最长公共前后缀。如下图：

我们可以根据第一个A来推导AB,再来推导ABA的最长公共前后缀，推导方法为：

  1. A只有一个，最长公共前后缀：0。

  1. AB，新增字符B，A和B不相等，最长公共前后缀：0。

  1. ABA，新增字符A，A和A相等，最长公共前后缀：1。

  1. ABAB，新增字符B，B和B（上一个最长公共前后缀：1为索引位的值为B）相等，最长公共前后缀：2。

  1. ABABC，新增字符C，C和A（上一个最长公共前后缀：2为索引位的值为A）不相等，这时需要计算前两位AB和后两位BC是否相等，不相等，最长公共前后缀：0。

  1. ABABCA，新增字符A，A和A（上一个最长公共前后缀：0,所以直接和头部的A比较）相等，最长公共前后缀：1。

  1. ABABCAB，新增字符B，B和B（上一个最长公共前后缀：1为索引位的值为B）相等，最长公共前后缀加一变为：2。

  1. ABABCABA，新增字符A，A和A（上一个最长公共前后缀：2为索引位的值为A）相等，最长公共前后缀加一变为：3。

再在前缀表的前面加-1主要是为了方便计算，就到了最终版前缀表。

前缀表PrefixTable，主串索引PrimaryStrIndex，模式串索引SubStrIndex，从0开始匹配，当匹配到4号索引位时和主串字符不同，SubStrIndex由4变为PrefixTable[4]也就是2，模式串的2号索引位为A，相等和主串索引4号位A，继续匹配。

当匹配到PrimaryStrIndex=6，SubStrIndex=4时，又不想等，将SubStrIndex置为PrefixTable[4]也就是2，模式串的2号索引位为A，相等和主串索引6号位A，继续匹配，发现全部匹配上，就OK了。

三、函数介绍

1、GetPrefixTable

（1）用途

给出字符串StrArray及其长度StrArrayLen，返回一个int类型的前缀表数组。

（2）源码

int* GetPrefixTable(char* StrArray, size_t StrArrayLen)
{int* PrefixTable        = (int*)malloc(sizeof(int) * StrArrayLen);PrefixTable[0]          = -1;if(StrArrayLen == 1){return PrefixTable;}PrefixTable[1]          = 0;size_t StrArrayIndex    = 1;size_t PrefixTableIndex;size_t i = 0;for(PrefixTableIndex = 2; PrefixTableIndex<StrArrayLen; PrefixTableIndex++,StrArrayIndex++){//printf("PrefixTableIndex : %ld, StrArrayIndex : %ld, PrefixTable[PrefixTableIndex-1] : %d\n",PrefixTableIndex,StrArrayIndex,PrefixTable[PrefixTableIndex-1]);if(PrefixTable[PrefixTableIndex-1] == 0) //如果前缀表的上一位的值为0，说明没有公共前后缀。{//printf("StrArray[0] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[0], StrArray[StrArrayIndex]);if(StrArray[0] == StrArray[StrArrayIndex]) //判断第一个字符和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] = 1;}else{PrefixTable[PrefixTableIndex] = 0;}}else{//printf("StrArray[PrefixTable[PrefixTableIndex-1]] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[PrefixTable[PrefixTableIndex-1]],StrArray[StrArrayIndex]);if(StrArray[PrefixTable[PrefixTableIndex-1]] == StrArray[StrArrayIndex])//判断上一个公共前缀最大长度的后一位和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1] + 1;}else{for(i=0; i<PrefixTable[PrefixTableIndex-1]; i++)//需要循环判断上一个公共前缀的每个字符和新子串的相应字符是否相等。如果上一个公共前缀最大长度是2，字符串aacaaa,那就需要判断前两个a和后两个a是否相等。{if(StrArray[i] != StrArray[StrArrayIndex-PrefixTable[PrefixTableIndex-1]+1+i]){PrefixTable[PrefixTableIndex] = 0;break;}}if(i == PrefixTable[PrefixTableIndex-1]){PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1];}}}//printf("PrefixTable[%ld] = %d\n",PrefixTableIndex,PrefixTable[PrefixTableIndex]);//printf("=====================\n");}return PrefixTable;
}

（3）参数

参数名

描述

StrArray

char*类型StrArray字符串。

StrArrayLen

size_t类型的StrArray长度。

2、KmpSearch

（1）用途

在主串PrimaryStr搜索第Times次出现的模式串SubStr，返回SubStr的首字符在PrimaryStr的索引位。如果匹配失败返回-1。

（2）源码

int KmpSearch(char* PrimaryStr, char* SubStr, int Times)
{if(PrimaryStr == NULL || SubStr == NULL){return -1;}if(Times < 1){return -1;}size_t      PrimaryStrLen = strlen(PrimaryStr);size_t      SubStrLen     = strlen(SubStr);if(SubStrLen > PrimaryStrLen){return -1;}else if(SubStrLen == PrimaryStrLen){if(strcmp(SubStr,PrimaryStr) == 0){return 0;}else{return -1;}}long long PrimaryStrIndex = 0;long long SubStrIndex     = 0;int Cnt                   = 0;//匹配次数和Times对应。 int* PrefixTable          = GetPrefixTable(SubStr, SubStrLen);PrintArray(PrimaryStr, PrimaryStrLen, sizeof(char));PrintArray(SubStr, SubStrLen, sizeof(char));PrintArray(PrefixTable, SubStrLen, sizeof(int));while(PrimaryStrIndex < PrimaryStrLen){if(PrimaryStr[PrimaryStrIndex] == SubStr[SubStrIndex]){PrimaryStrIndex++;SubStrIndex++;if(SubStrIndex == SubStrLen){Cnt++;if(Cnt == Times){return PrimaryStrIndex - SubStrIndex;}SubStrIndex--;SubStrIndex = PrefixTable[SubStrIndex];}}else{SubStrIndex = PrefixTable[SubStrIndex];if(SubStrIndex == -1){PrimaryStrIndex++;SubStrIndex++;}}}free(PrefixTable);return -1;
}

（3）参数

参数名

描述

PrimaryStr

char*类型主串。

SubStr

char*类型模式串。

Times

匹配第几次

四、虚机测试源码

# include<stdio.h>
# include<string.h>
# include<stdlib.h>int* GetPrefixTable(char* StrArray, size_t StrArrayLen);
int KmpSearch(char* PrimaryStr, char* SubStr, int Times);
void PrintArray(void* Array, size_t ArrayLen, size_t TypeFlag);int main()
{char* PrimaryStr = "ABABABABCABAAB";char* SubStr     = "ABABCABAA";printf("Position : %d\n",KmpSearch(PrimaryStr, SubStr, 1));return 0;
}int* GetPrefixTable(char* StrArray, size_t StrArrayLen)
{int* PrefixTable        = (int*)malloc(sizeof(int) * StrArrayLen);PrefixTable[0]          = -1;if(StrArrayLen == 1){return PrefixTable;}PrefixTable[1]          = 0;size_t StrArrayIndex    = 1;size_t PrefixTableIndex;size_t i = 0;for(PrefixTableIndex = 2; PrefixTableIndex<StrArrayLen; PrefixTableIndex++,StrArrayIndex++){//printf("PrefixTableIndex : %ld, StrArrayIndex : %ld, PrefixTable[PrefixTableIndex-1] : %d\n",PrefixTableIndex,StrArrayIndex,PrefixTable[PrefixTableIndex-1]);if(PrefixTable[PrefixTableIndex-1] == 0) //如果前缀表的上一位的值为0，说明没有公共前后缀。{//printf("StrArray[0] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[0], StrArray[StrArrayIndex]);if(StrArray[0] == StrArray[StrArrayIndex]) //判断第一个字符和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] = 1;}else{PrefixTable[PrefixTableIndex] = 0;}}else{//printf("StrArray[PrefixTable[PrefixTableIndex-1]] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[PrefixTable[PrefixTableIndex-1]],StrArray[StrArrayIndex]);if(StrArray[PrefixTable[PrefixTableIndex-1]] == StrArray[StrArrayIndex])//判断上一个公共前缀最大长度的后一位和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1] + 1;}else{for(i=0; i<PrefixTable[PrefixTableIndex-1]; i++)//需要循环判断上一个公共前缀的每个字符和新子串的相应字符是否相等。如果上一个公共前缀最大长度是2，字符串aacaaa,那就需要判断前两个a和后两个a是否相等。{if(StrArray[i] != StrArray[StrArrayIndex-PrefixTable[PrefixTableIndex-1]+1+i]){PrefixTable[PrefixTableIndex] = 0;break;}}if(i == PrefixTable[PrefixTableIndex-1]){PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1];}}}//printf("PrefixTable[%ld] = %d\n",PrefixTableIndex,PrefixTable[PrefixTableIndex]);//printf("=====================\n");}return PrefixTable;
}int KmpSearch(char* PrimaryStr, char* SubStr, int Times)
{if(PrimaryStr == NULL || SubStr == NULL){return -1;}size_t      PrimaryStrLen = strlen(PrimaryStr);size_t      SubStrLen     = strlen(SubStr);if(SubStrLen > PrimaryStrLen){return -1;}else if(SubStrLen == PrimaryStrLen){if(strcmp(SubStr,PrimaryStr) == 0){return 0;}else{return -1;}}long long PrimaryStrIndex = 0;long long SubStrIndex     = 0;int Cnt                   = 0;//匹配次数和Times对应。 int* PrefixTable          = GetPrefixTable(SubStr, SubStrLen);PrintArray(PrimaryStr, PrimaryStrLen, sizeof(char));PrintArray(SubStr, SubStrLen, sizeof(char));PrintArray(PrefixTable, SubStrLen, sizeof(int));while(PrimaryStrIndex < PrimaryStrLen){if(PrimaryStr[PrimaryStrIndex] == SubStr[SubStrIndex]){PrimaryStrIndex++;SubStrIndex++;if(SubStrIndex == SubStrLen){Cnt++;if(Cnt == Times){return PrimaryStrIndex - SubStrIndex;}SubStrIndex--;SubStrIndex = PrefixTable[SubStrIndex];}}else{SubStrIndex = PrefixTable[SubStrIndex];if(SubStrIndex == -1){PrimaryStrIndex++;SubStrIndex++;}}}free(PrefixTable);return -1;
}void PrintArray(void* Array, size_t ArrayLen, size_t TypeFlag)
{size_t i;printf("Array    : ");for(i = 0; i < ArrayLen; i++){switch(TypeFlag){case sizeof(int)  : printf("%d ",((int*)Array)[i]); break;case sizeof(char) : printf("%c ",((char*)Array)[i]); break;default : printf("Unknow Type!!!\n" );}}printf("\n==================================\n");
}

五、虚机测试

[gbase@czg2 LinearTable_String_KMP]$ make
gcc -Wall -g KmpSearch.c -o Test_KmpSearch [gbase@czg2 LinearTable_String_KMP]$ ./Test_KmpSearch 
Array    : A B A B A B A B C A B A A B 
==================================
Array    : A B A B C A B A A 
==================================
Array    : -1 0 0 1 2 0 1 2 3 
==================================
Position : 4

六、Leecode提交源码

int* GetPrefixTable(char* StrArray, size_t StrArrayLen);
int KmpSearch(char* PrimaryStr, char* SubStr, int Times);int strStr(char * haystack, char * needle){return KmpSearch(haystack, needle, 1);
}int* GetPrefixTable(char* StrArray, size_t StrArrayLen)
{int* PrefixTable        = (int*)malloc(sizeof(int) * StrArrayLen);PrefixTable[0]          = -1;if(StrArrayLen == 1){return PrefixTable;}PrefixTable[1]          = 0;size_t StrArrayIndex    = 1;size_t PrefixTableIndex;int i = 0;for(PrefixTableIndex = 2; PrefixTableIndex<StrArrayLen; PrefixTableIndex++,StrArrayIndex++){//printf("PrefixTableIndex : %ld, StrArrayIndex : %ld, PrefixTable[PrefixTableIndex-1] : %d\n",PrefixTableIndex,StrArrayIndex,PrefixTable[PrefixTableIndex-1]);if(PrefixTable[PrefixTableIndex-1] == 0) //如果前缀表的上一位的值为0，说明没有公共前后缀。{//printf("StrArray[0] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[0], StrArray[StrArrayIndex]);if(StrArray[0] == StrArray[StrArrayIndex]) //判断第一个字符和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] = 1;}else{PrefixTable[PrefixTableIndex] = 0;}}else{//printf("StrArray[PrefixTable[PrefixTableIndex-1]] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[PrefixTable[PrefixTableIndex-1]],StrArray[StrArrayIndex]);if(StrArray[PrefixTable[PrefixTableIndex-1]] == StrArray[StrArrayIndex])//判断上一个公共前缀最大长度的后一位和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1] + 1;}else{for(i=0; i<PrefixTable[PrefixTableIndex-1]; i++){if(StrArray[i] != StrArray[StrArrayIndex-PrefixTable[PrefixTableIndex-1]+1+i]){PrefixTable[PrefixTableIndex] = 0;break;}}if(i == PrefixTable[PrefixTableIndex-1]){PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1];}}}//printf("PrefixTable[%ld] = %d\n",PrefixTableIndex,PrefixTable[PrefixTableIndex]);//printf("=====================\n");}return PrefixTable;
}int KmpSearch(char* PrimaryStr, char* SubStr, int Times)
{if(PrimaryStr == NULL || SubStr == NULL){return -1;}size_t      PrimaryStrLen = strlen(PrimaryStr);size_t      SubStrLen     = strlen(SubStr);if(SubStrLen > PrimaryStrLen){return -1;}else if(SubStrLen == PrimaryStrLen){if(strcmp(SubStr,PrimaryStr) == 0){return 0;}else{return -1;}}long long PrimaryStrIndex = 0;long long SubStrIndex     = 0;int Cnt                   = 0;//匹配次数和Times对应。 int* PrefixTable          = GetPrefixTable(SubStr, SubStrLen);//PrintArray(PrimaryStr, PrimaryStrLen, sizeof(char));//PrintArray(SubStr, SubStrLen, sizeof(char));//PrintArray(PrefixTable, SubStrLen, sizeof(int));while(PrimaryStrIndex < PrimaryStrLen){if(PrimaryStr[PrimaryStrIndex] == SubStr[SubStrIndex]){PrimaryStrIndex++;SubStrIndex++;if(SubStrIndex == SubStrLen){Cnt++;if(Cnt == Times){return PrimaryStrIndex - SubStrIndex;}SubStrIndex--;SubStrIndex = PrefixTable[SubStrIndex];}}else{SubStrIndex = PrefixTable[SubStrIndex];if(SubStrIndex == -1){PrimaryStrIndex++;SubStrIndex++;}}}free(PrefixTable);return -1;
}void PrintArray(void* Array, size_t ArrayLen, size_t TypeFlag)
{size_t i;printf("Array    : ");for(i = 0; i < ArrayLen; i++){switch(TypeFlag){case sizeof(int)  : printf("%d ",((int*)Array)[i]); break;case sizeof(char) : printf("%c ",((char*)Array)[i]); break;default : printf("Unknow Type!!!\n" );}}printf("\n==================================\n");
}

七、Leecode通过截图

http://www.dt0577.cn/news/51510.html

相关文章：

  • 山东网站建设和游戏开发的公司阿里域名购买网站
  • 人力资源公司简介模板短视频关键词seo优化
  • 代理做网站合适吗盘古百度推广靠谱吗
  • 保定市做网站郑州网站营销推广
  • wordpress 开发主题百度网站优化工具
  • 企业做网站的作用网络优化工程师需要学什么
  • 云南网站建设的价值seo牛人
  • 百度注册入口sem推广优化
  • 专做影视评论的网站百度seo2022
  • 鹤壁网站优化山西疫情最新情况
  • xml文件里做网站超链接南宁百度seo公司
  • 数据库型网站百度网页推广费用
  • 网站客服在线系统外汇交易平台
  • 网站建设报表明细东营seo整站优化
  • 做一个商城网站需要多少钱推广网站源码
  • 政府网站集约化建设存在的问题国家免费职业技能培训官网
  • 闸北网站建设电商如何从零做起
  • 杭州优质网站建设怎样推广自己的app
  • 网站 做英文 翻译 规则武汉百捷集团百度推广服务有限公司
  • 携程旅行网站建设分析网络推广关键词优化公司
  • 做电影网站违法么百度推广客服电话人工服务
  • 如何建设购物网站国际新闻头条今日要闻
  • top模板wordpressseo和sem的区别是什么?
  • 跨境电商网站建设网站加速
  • 网站建设相关论文域名whois查询
  • 广州建设网站外包云推广
  • 广州市品牌网站建设平台南京百度提升优化
  • 建网站做淘宝客免费发布推广的平台
  • 图怪兽在线制作企业网站seo优化公司
  • 网站备份文件深圳网站开发