WHCSRL 技术网

# KMP与题目练习

``````#include<iostream>
using namespace std;
int ne;
typedef struct{
char data;
int length;
}Sstring; //串的数据结构
//Sstring 是串的数据结构
//typedef重命名结构体变量，可以用Sstring t 定义一个结构体。
Sstring s,t;
void Getnext(){
int j = 0,k = -1;
ne = -1; //一定要设置初值！！
while(j < t.length-1){
if(k=-1||t.data[j]==t.data[k]){
ne[++j] = ++k; //最后一次进来的时候 j= t.length -2  出去就变为了 length-1了
}else k = ne[k]; //前缀的前缀
}
}
int KMPget(){
int i = 0,j = 0;
Getnext();
while(i < s.length&&j<t.length){
if(j==-1||s.data [i]==t.data [j]){ //相等就双指针 往前移  也有可能从头开始匹配
i++;j++;
}else j = ne[j];
}
if(j>=t.length) {
return i- t.length; //这里的i已经是length了所以可以直接减去t.length
}else return -1;
}
int main(){
int n,m;
cin>>m>>t.data>>n>>s.data;
s.length = n;
t.length = m;
int ans = KMPget();
cout<<ans<<endl;
return 0;
}
```12345678910111213141516171819202122232425262728293031323334353637383940```

``````#include <bits/stdc++.h>
using namespace std;

int main(void)
{
vector<int> v;
v.push_back(1);
unsigned int a=-1;
cout<<a<<endl;
cout<<(-1>=v.size())<<endl;
return 0;
}
```123456789101112```

（vector.size()的一些常见错误总结）