一些KMP的题目

news/2024/9/22 20:33:22/

普通的KMP代码：

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int nexts[10000],k;
void get_nexts(string t)
{nexts[0] = -1;int i = 0, j = -1;int len = t.size();while(i < len) {if(j == -1 || t[i] == t[j])nexts[++i] = ++j;elsej = nexts[j];}k=i;
}
bool KMP(string s,string t)
{get_nexts(t);int len1 = t.size();int len2 = s.size();int i = 0, j = 0;while( j < len2 ) {if( t[i] == s[j] ) {i++;j++;if( i == len1 ) {return true;}}else {i = nexts[i];if( i == -1 ){j++;i++;}}}return false;
}
int main()
{   sizeof(nexts,0,sizeof(nexts));string s,t;cin>>s>>t;cout<<KMP(s,t)<<endl;
return 0;
}

题目总结：
POJ 2752
POJ2406
POJ1961
POJ3461
HDU1711
HDU2087
HDU2203亲和串
HDU3746
HDU2594
HDU3336
HDU2328
正题：
POJ - 2752
The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:

Step1. Connect the father’s name and the mother’s name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).

Example: Father=‘ala’, Mother=‘la’, we have S = ‘ala’+‘la’ = ‘alala’. Potential prefix-suffix strings of S are {‘a’, ‘ala’, ‘alala’}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)
Input
The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Output
For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby’s name.
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int ne[500000];
void getnext(string k)
{ne[0]=-1;int i=0,j=-1;int len = k.size();while(i < len){if(j == -1 || k[i] == k[j]) {ne[++i] = ++j;}else {j = ne[j];}}
}
int main()
{   memset(ne,0,sizeof(ne));string s;int a[500000];while(cin >> s){   int n;n=0;getnext(s);int len = s.size();a[n++] = len;while(len){a[n++] = ne[len];len = ne[len];}n--;for(int i = n-1;i >= 0;i--) {if(i!=0) cout<<a[i]<<" ";else cout<<a[i]<<endl;}}
return 0;
}
/*有了kmp算法的next数组（保存某段子串的相同前后缀的最大长度，不包括自身），
可以从最长的相同前后缀开始考虑，对于串S，根据next[strlen(S)-1]得到的最长相
同前后缀为S1,则再根据next[strlen(S1)-1]得到的S1的最长相同前后缀S2肯定也为S
的相同前后缀。（通过画图可以很容易的证明）。*/

POJ2406
Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).
Input
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
Output
For each s you should print the largest n such that s = a^n for some string a.
Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int ne[1000010],k;
void getnext(string s,int len)
{ne[0] = -1;int i=0,j=-1;while(i < len) {if(j == -1 || s[i] == s[j]){ne[++i] = ++j;}else {j = ne[j];}}
}
int main()
{   IOS;string s;while(cin >> s && s != "." ) {int n = s.size();getnext(s,n);int m = n - ne[n];if(n%m==0) {cout<<(n/m)<<endl;}else {cout<< 1 <<endl;}}
return 0;
}
/*此题关键在于求出最长循环节的长度，假设一个字符串长
度为n，循环节长度为m，假设一个字符串是由K个子串组成的
，则字符串最后一个字符的NEXT数值一定是K-1个子串的长度，
所以只需求出NEXT[N]后N-NEXT[N]就是可能的最长循环节，但
是如果N-NEXT[N]不能整除N，则一定原字符串无循环，所以最
后模判定一下就行了*/

POJ1961
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.
Input
The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S.The second line contains the string S. The input file ends with a line, having the
number zero on it.
Output
For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.
Sample Input
3
aaa
12
aabaabaabaab
0
Sample Output
Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int ne[1000010],k;
void getnext(string s,int m)
{ne[0] = -1;int i=0,j=-1;int len = m;while(i < len) {if(j == -1 || s[i] == s[j]){ne[++i] = ++j;}else {j = ne[j];}}
}
int main()
{   IOS;int k=1,m;string s;while(cin>>m&&m!=0) {cin>>s;cout<<"Test case #"<<k++<<endl;getnext(s,m);for( int i = 2;i <= m;i++) {int t = i - ne[i];if(i%t==0&&(i/t)!=1) {cout<<i<<" "<<(i/t)<<endl;}}cout<<endl;}
return 0;
}
/*这道题好像就是POJ 2406的加强版而已。那道题是输出
一个字符串的循环节出现的次数，这个是到第i个字符为止
，其实就是多了一层循环。把这个字符串遍历一次即可。*/

POJ3461
The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter ‘e’. He was a member of the Oulipo group. A quote from the book:

Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…

Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T’s is not unusual. And they never use spaces.

So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {‘A’, ‘B’, ‘C’, …, ‘Z’} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.

Input
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

One line with the word W, a string over {‘A’, ‘B’, ‘C’, …, ‘Z’}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
One line with the text T, a string over {‘A’, ‘B’, ‘C’, …, ‘Z’}, with |W| ≤ |T| ≤ 1,000,000.
Output
For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int ne[1000005],ans;
void getnext(string s,int len)
{ne[0] = -1;int i=0,j=-1;while(i < len){if(j == -1 || s[i] == s[j] ){ne[++i] = ++j;}else {j = ne[j];}}
}
void KMP(string t,string s, int lent,int lens)
{int i=0,j=0;while(i<lens) {if(j == -1 || s[i] == t[j]){i++;j++;if(j == lent) {ans++;j= ne[j];}}else {j = ne[j];}}
}
int main()
{   IOS;int k;cin>>k;string s,t;while(k--) {cin>>t>>s;ans=0;int lent = t.size();int lens = s.size();getnext(t,lent);KMP(t,s,lent,lens);cout<<ans<<endl;}
return 0;
}

HDU1711

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
#define ll long long
int nexts[1000005],s[1000005],t[1000005],n,m;
void getnext()
{int i = 0,j = -1;nexts[0] = -1;while(i < m){if(j == -1 || t[i] == t[j]) {nexts[++i] = ++j;}else j = nexts[j];}
}
int kmp()
{   getnext();int i,j;i = j = 0;while(i < n){if(j == -1 || s[i] == t[j]){i++;j++;if(j == m){return i - m;}}else j = nexts[j];}return -1;
}
int main()
{   IOS;int T;cin>>T;while(T--) {cin>>n>>m;for(int i = 0;i < n;i++){cin>>s[i];}for(int i = 0;i < m;i++){cin>>t[i];}int ans = kmp();if(ans != -1) cout<<ans+1<<endl;else cout<<-1<<endl;}return 0;
}

HDU2087
(水题)
HDU2203亲和串
（把主串复制一遍接在主串后面，再进行kmp即可）
HDU3746

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
#define ll long long
string t;
int nexts[100555];
void getnext()
{int len = t.size();int i = 0,j = -1;nexts[0] = -1;while(i < len){if(j == -1|| t[i] == t[j]){nexts[++i] = ++j;}else j = nexts[j];}
}
int main()
{   IOS;int n;cin>>n;while(n--){cin>>t;getnext();int len = t.size();if(nexts[len] == 0) cout<<len<<endl;else {if(len%(len - nexts[len]) == 0) cout<<0<<endl;else cout<<(len - nexts[len]) - len%(len - nexts[len])<<endl;}}return 0;
}

HDU2594

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
#define ll long long
string s,t,ans;
int nexts[500055];
void getnext()
{int len = t.size();int i = 0,j = -1;nexts[0] = -1;while(i < len){if(j == -1|| t[i] == t[j]){nexts[++i] = ++j;}else j = nexts[j];}
}
void kmp()
{getnext();int i=0;int j=0;while( i < s.size() ){if(j == -1||s[i] == t[j]){i++;j++;}elsej=nexts[j];}if(!j)cout<<j<<endl;else{for(int k=0;k<j;k++)cout<<t[k];cout<<" "<<j<<endl;}
}
int main()
{   IOS;while(cin>>t>>s){kmp();}return 0;
}

*HDU3336

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
#define ll long long
string t;
int nexts[200005];
void getnext()
{int len = t.size();int i = 0,j = -1;nexts[0] = -1;while(i < len){if(j == -1|| t[i] == t[j]){nexts[++i] = ++j;}else j = nexts[j];}
}
int main()
{   IOS;int T,len;cin>>T;while(T--){cin>>len>>t;getnext();int ans = len % 10007;for(int i = 1;i <= len;i++) if(nexts[i] != 0) ans = (ans+1) %10007;cout<<ans<<endl;}return 0;
}

HDU2328

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int ne[1015];
void getnext(string s,int len)
{int i = 0;ne[0] = -1;int j = -1;while(i < len){if(j == -1 ||s[i] == s[j]){i++;j++;if(s[i] != s[j]) ne[i] = j;else ne[i] = ne[j];}else j = ne[j];}
}
int KMP(string t,string s, int lent,int lens)
{   getnext(t,lent);int i=0,j=0;while(i<lens) {if(j == -1 || s[i] == t[j]){i++;j++;if(j == lent) {return 1;}}else {j = ne[j];}}return 0;
}
int main()
{   IOS;int N;string s[4015];while(cin>>N && N){int k,len;len = inf;for(int i = 1;i <= N;i++){cin>>s[i];if(len > s[i].size()) {len = s[i].size();k = i;}}int flag = 0;string ans,ant;for(int i = len;i >= 1;i--){if(ans.size() > i) break;for(int j = 0; i + j <= len;j++){ant.clear();int h;for( h = j; h < i + j;h++){ant += s[k][h];}for( h = 1;h <= N;h++){if(h == k) continue;if(KMP(ant,s[h],ant.size(),s[h].size())) continue;else break;}if(h == N+1) {if(!flag) {ans = ant;flag = 1;}else {if(ans.size() > ant.size()) continue;else {if(ans > ant) ans = ant;}}}}}if(ans.size() == 0) cout<<"IDENTITY LOST"<<endl;else cout<<ans<<endl;}
return 0;
}

http://www.ppmy.cn/news/735263.html

相关文章

kmp算法模板题

kmp算法模板题

剪花布条 一块花布条&#xff0c;里面有些图案&#xff0c;另有一块直接可用的小饰条&#xff0c;里面也有一些图案。对于给定的花布条和小饰条&#xff0c;计算一下能从花布条中尽可能剪出几块小饰条来呢&#xff1f; Input 输入中含有一些数据&#xff0c;分别是成对出现的花…
阅读更多...
摄像机标定和图像径向畸变校正

摄像机标定和图像径向畸变校正

这段时间断断续续在弄这个摄像头的标定和图像畸形矫正的问题&#xff0c;基本差不多了&#xff0c;乘休息时间&#xff0c;发点成果和大家分享吧&#xff01; 一、标定 关于摄像头的标定&#xff0c;说实话网上的资料太多了&#xff0c;方法也很多的。个人觉得想要研究这个的话…
阅读更多...
ESP8266类库的使用——总体概述

ESP8266类库的使用——总体概述

在文章《ArduinoESP8266连接WiFi》与文章《ESP8266联网测试》中&#xff0c;我们通过查询ESP8266的AT指令&#xff0c;编写相应的函数实现ESP8266连接WiFi的功能。但是连接WiFi只是芯片的功能之一&#xff0c;为了实现物联网的目的&#xff0c;我们还有更远的路要走。 君子善假…
阅读更多...
未检测到扫描仪Win10解决 WIA服务1061

未检测到扫描仪Win10解决 WIA服务1061

之前正常使用的扫描仪&#xff0c;突然不能用了&#xff0c;出现未检测到扫描仪错误 Windows画图板的文件菜单里从扫描仪或相机获取而已是灰色的。 网上搜索解决方案&#xff0c;一堆垃圾文章&#xff0c;毫无帮助。在设备管理器里查看图像设备是在的&#xff0c;确定驱动没有…
阅读更多...
keil4与proteus的联调

keil4与proteus的联调

联调 顾名思义即是联合调试的意思&#xff0c;是指keil4与proteus联合调试&#xff0c;在进行联调是需要做好以下配置的。 1.第一步是将.DLL文复制到安装keil路径的BIN目录&#xff0c;所以一定要记住自己把keil装在哪儿了,博文下面有需要的.DLL文件。 2.万一忘记了自己装在哪…
阅读更多...
ActiveX控件v7.2.0.1,Viscom Scanner ActiveX控件

ActiveX控件v7.2.0.1,Viscom Scanner ActiveX控件

ActiveX控件能够使用带有进纸器的扫描仪扫描多页&#xff0c;在最后一页扫描时自动保存为多页PDF或TIFF。 ActiveX控件有能力检测卡纸事件。q2315702359 ActiveX控件从所有TWAIN兼容扫描仪和网络摄像头设备捕获图像。 支持将扫描的图像保存到 Microsoft Word(docx)。 ActiveX控…
阅读更多...
正点原子IMX6UL IIC RTC驱动DS3231

正点原子IMX6UL IIC RTC驱动DS3231

1 前言 觉得Imx6内部的RTC时钟不是很准,于是外置RTC芯片ds3231 在源码里一查, 发现在driver/rtc/rtc-ds1307.c中 2 修改设备树 ds3231地址可以查询数据表: 0xd0 , 但是linux 设备树要右移一位, 于是就成了0x68 也可以通过i2ctest来检测地址 &i2c1 {clock-frequency <…
阅读更多...
《ESP32-Arduino开发》GUI设计 LVGL 开发环境搭建教程（从工程目录到模拟器）

《ESP32-Arduino开发》GUI设计 LVGL 开发环境搭建教程（从工程目录到模拟器）

前言&#xff1a;最近闲着无聊&#xff0c;看到手头正好有一块tft彩屏&#xff0c;想着拿来玩玩。既然用到了显示屏&#xff0c;自然是离不开ui设计&#xff0c;lvgl是嵌入式一个开源图形库&#xff0c;具备“Light”(轻量)和"Versatile"(可用性强)等特点。对于我而言…
阅读更多...
最新文章

Copyright @ 2022~2023