hdu1711(kmp纯模板)

Dear 丶 2021-12-22 09:55 177阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

void  get\_next()  
\{  
 int  i =- 1 ,j = 0 ;  
next\[ 0 \] =- 1 ;  
 while (j < m \- 1 )  
\{  
 if (i ==- 1 || b\[i\] == b\[j\]) \{  \++ i;  \++ j; next\[j\] = i;\}  
 else  i = next\[i\];  
\}  
\}  
 int  Index\_KMP()  
\{  
 int  i = 0 ,j = 0 ;  
 while (i < n  &&  j < m)  
\{  
 if (a\[i\] == b\[j\] || j ==- 1 ) \{  \++ i;  \++ j;\}  
 else  j = next\[j\];  
\}  
 if (j >= m)  return  i \- m \+ 1 ;  
 else  return  \- 1 ;  
\}

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

\#include < iostream >   
 \#define  M 10001   
 \#define  N 1000001   
 using  namespace  std;  
\_\_int64 a\[N\],b\[M\];  
 int  next\[M\];  
 int  t,n,m;  
 void  get\_next()  
\{  
 int  i =- 1 ,j = 0 ;  
next\[ 0 \]  =  \- 1 ;  
 while (j < m \- 1 )  
\{  
 if (i ==- 1  ||  b\[i\] == b\[j\])  
\{  
i \++ ;  
j \++ ;  
next\[j\]  =  i;  
\}  
 else  i = next\[i\];  
\}  
\}  
  
 int  Index\_KMP()  
\{  
 int  i = 0 ,j = 0 ;  
 while (i < n  &&  j < m)  
\{  
 if (a\[i\]  ==  b\[j\]  ||  j ==- 1 )  
\{  
i \++ ;  
j \++ ;  
\}  
 else  j = next\[j\];  
\}  
 if (j >= m)  return  i \- m \+ 1 ;  
 else  return  \- 1 ;  
\}  
 int  main()  
\{  
  
 int  i,j;  
scanf( " %d " , & t);  
 while (t \-- )  
\{  
scanf( " %d%d " , & n, & m);  
  
 for (i = 0 ;i < n;i \++ ) scanf( " %d " , & a\[i\]);  
 for (i = 0 ;i < m;i \++ )scanf( " %d " , & b\[i\]);  
get\_next();  
printf( " %d\\n " ,Index\_KMP());  
  
\}  
 return  0 ;  
\}

转载于:https://www.cnblogs.com/FCWORLD/archive/2011/04/08/2009019.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/fa051cb971c446d7adf77685b0a1feb8.png

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1711 Number Sequence （KMP模板题）

Number Sequence Problem Description Given two sequences of numbers : a\[1\], a\

谁借莪１个温暖的怀抱￠/ 2024年02月17日 21:12/ 0 赞/ 13 阅读

相关 [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher A - Number Sequence HDU - 1711 (kmp)

\[kuangbin带你飞\]专题十六 KMP & 扩展KMP & Manacher A - Number Sequence HDU - 1711 题目链接

小鱼儿/ 2023年08月17日 15:41/ 0 赞/ 102 阅读

相关 HDU 1711 Number Sequence

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768

淩亂°似流年/ 2022年09月29日 15:53/ 0 赞/ 138 阅读

相关 HDU 1711 Number Sequence //简单kmp

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (

忘是亡心i/ 2022年08月23日 11:54/ 0 赞/ 134 阅读

相关 hdu 1711 KMP模版题

[点击打开链接][Link 1] 题意: 找模式串在文本串中首次出现的位置; 分析:, 数据量比较大, 因此要用KMP来解决,套上KMP模版就行了;

冷不防/ 2022年07月26日 05:23/ 0 赞/ 125 阅读

相关 HDU - 1711 Number Sequence （KMP）

Number Sequence Problem Description Given two se

ゞ浴缸里的玫瑰/ 2022年05月19日 07:50/ 0 赞/ 196 阅读

相关 Hdu 1711 Number Sequence(KMP模板题)

[传送门][Link 1] 题意：给你一个长度为N的文本串（1 <= N <= 1000000），和一个长度为M的模式串（1 <= M <= 10000），如果文本串中不存在

缺乏、安全感/ 2022年05月19日 06:56/ 0 赞/ 184 阅读

相关 HDU 1711 Number Sequence——————KMP 模板题

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (

素颜马尾好姑娘i/ 2022年05月16日 08:54/ 0 赞/ 155 阅读

相关 kmp1-HDU1711 HDU1686 HDU2087 HDU3746

HDU 1711 kmp模板题 [http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_sh

叁歲伎倆/ 2022年05月14日 11:24/ 0 赞/ 157 阅读

相关 hdu1711(kmp纯模板)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] void get\_next() \{ int

Dear 丶/ 2021年12月22日 09:55/ 0 赞/ 178 阅读