KMP与最小覆盖子串

poj 2752题目链接 题意：求出所有的前缀和后缀相同的子串的长度。 思路：求出nxt函数，观察发现，从从len递归向前就是答案。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月10日 星期三 21时05分52秒 4File Name :code/poj/2752.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <stack> 14#include <set> 15#include <map> 16#include <string> 17#include <cmath> 18#include <cstdlib> 19#include <deque> 20#include <ctime> 21#define fst first 22#define sec second 23#define lson l,m,rt<<1 24#define rson m+1,r,rt<<1|1 25#define ms(a,x) memset(a,x,sizeof(a)) 26typedef long long LL; 27#define pi pair < int ,int > 28#define MP make_pair 29 30using namespace std; 31const double eps = 1E-8; 32const int dx4[4]={1,0,0,-1}; 33const int dy4[4]={0,-1,1,0}; 34const int inf = 0x3f3f3f3f; 35const int N=4E6+7; 36int n; 37string a; 38int nxt[N]; 39void getnxt( int n) 40{ 41 int i = 0 ; 42 int j = -1 ; 43 nxt[0] = -1; 44 while (i<n) 45 if (j==-1||a[i]==a[j]) nxt[++i]=++j; 46 else j = nxt[j]; 47} 48void print( int x) 49{ 50 if (nxt[x]!=-1) 51 { 52 print(nxt[x]); 53 printf("%d ",x); 54 } 55} 56int main() 57{ 58 #ifndef ONLINE_JUDGE 59 freopen("code/in.txt","r",stdin); 60 #endif 61// ios::sync_with_stdio(false); 62 while (cin>>a) 63 { 64 int len = a.length(); 65 getnxt(len); 66 // for ( int i = 0 ; i < len ; i++) cout<<i<<" nxt[i]:"<<nxt[i]<<endl; 67 print(nxt[len]); 68 printf("%d\n",len); 69 70 } 71 72 #ifndef ONLINE_JUDGE 73 fclose(stdin); 74 #endif 75 return 0; 76}

hdu1686 题意：给出模式串和文本串，问模式串在文本串中出现了多少次，可以overlap. 思路：思考naive的匹配过程。nxt函数不过是改进了当失配发生时，不是移动1位，而是移动多位。nxt函数的含义是当失配发生时，移动到的位置….所以有的教程管这个叫失配函数吧，也不是很难理解的样子。

20170801update：当时竟然没有强调 next 函数的含义？ next[i] 的含义是，i 之前的整个前缀中，最长的「前缀和后缀相同」的长度。 看图： KMP 感觉是我学到现在最难懂的一个算法了 QAQ 为什么你们都那么强啊，看几个小时就看懂了……

poj 2406 题意：给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的， 求 R 的最大值 思路：论文题。 转载论文中的题解： 做法比较简单，穷举字符串 S 的长度 k，然后判断是否满足。判断的时候， 先看字符串 L 的长度能否被 k 整除，再看 suffix(1) 和 suffix(k+1) 的最长公共前缀是否等于 n-k。在询问最长公共前缀的时候，suffix(1) 是固定的，所以 RMQ 问题没有必要做所有的预处理，只需求出 height 数组中的每一个数到 height[rank[1]] 之间的最小值即可。整个做法的时间复杂度为 O(n)

题目链接 傻逼模拟。。读完题就ac了。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月07日 星期日 18时04分18秒 4File Name :code/whust2016/#1/D.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=280; 34int n,m; 35int total,adva,advb; 36struct Friend 37{ 38 int money; 39 int adv; 40}f[N]; 41struct Room 42{ 43 int type; 44 int cost; 45 int adv; 46}r[N]; 47struct Ans 48{ 49 int val; 50 int rid; 51 int fid; 52 bool operator < (Ans b)const 53 { 54 return val>b.val; 55 } 56}ans[300*300]; 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 cin>>total>>adva>>advb; 63 cin>>n; 64 for ( int i = 1 ; i <= n ; i++) 65 scanf("%d %d",&f[i].money,&f[i].adv); 66 scanf("%d",&m); 67 for ( int i = 1 ; i <= m ; i++) 68 scanf("%d%d%d",&r[i].type,&r[i].cost,&r[i].adv); 69 int cnt = 0 ; 70 for ( int i = 1 ; i <= m ; i++) 71 { 72 if (r[i].type==1) 73 { 74 if (r[i].cost<=total) 75 { 76 cnt++; 77 ans[cnt].val = r[i].adv+adva; 78 ans[cnt].rid = i; 79 ans[cnt].fid = -1; 80 } 81 continue; 82 } 83 else 84 { 85 for ( int j = 0 ; j <= n ; j++) 86 { 87 if (j==0) //自己住双人间 88 { 89 if (r[i].cost<=total) 90 { 91 cnt++; 92 ans[cnt].val = r[i].adv+advb; 93 ans[cnt].rid = i ; 94 ans[cnt].fid = -1; 95 } 96 } 97 else 98 { 99 if (r[i].cost<=total*2&&r[i].cost<=f[j].money*2) 100 { 101 cnt++; 102 ans[cnt].val = r[i].adv+f[j].adv; 103 ans[cnt].rid = i ; 104 ans[cnt].fid = j; 105 } 106 } 107 } 108 } 109 } 110// for ( int i = 1 ; i <= cnt ; i++) 111// { 112// printf("val:%d room: %d friend : %d \n",ans[i].val,ans[i].rid,ans[i].fid); 113// } 114 if (cnt==0) 115 { 116 puts("Forget about apartments. Live in the dormitory."); 117 }else 118 { 119 sort(ans+1,ans+cnt+1); 120 if (r[ans[1].rid].type==1) 121 { 122 printf("You should rent the apartment #%d alone.\n",ans[1].rid); 123 } 124 else 125 { 126 if (ans[1].fid==-1) 127 { 128 printf("You should rent the apartment #%d alone.\n",ans[1].rid); 129 } 130 else 131 { 132 133 printf("You should rent the apartment #%d with the friend #%d.\n",ans[1].rid,ans[1].fid); 134 135 } 136 } 137 } 138 #ifndef ONLINE_JUDGE 139 fclose(stdin); 140 #endif 141 return 0; 142}