Posts

uva 1314 题目链接 题意：给定一个循环字符串，问字典序最小的串的开始位置。最小表示法裸题。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 18时48分29秒 4File Name :code/uva/1314.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=1E5+7; 34int n ; 35char s[N]; 36int minRep(char *s) 37{ 38 int n = strlen(s); 39 int i = 0; 40 int j = 1; 41 int k = 0; 42 while (i<n&&j<n&&k<n) 43 { 44 int t = s[(i+k)%n]-s[(j+k)%n]; 45 if (t==0) k++; 46 else 47 { 48 if (t>0) 49 i+=k+1; 50 else j+=k+1; 51 if (i==j) j++; 52 k = 0 ; 53 } 54 } 55 return i<j?i:j; 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%d\n%s",&n,s); 67 printf("%d\n",minRep(s)); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}

首先放一波资料： 参考博客 对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。 一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置，j作为比较指针。

hdu 4300题目链接 吐槽：题意难懂的一逼，关键的地方根本没有说清好么。。。竟然还是多校题。。。。出题人英语是体育老师教的吧。。？本来挺傻逼一道题。。被这完全没有说清楚的题意搞得很不爽。。。

hdu 3336 题目链接 题意：给一个字符串，问这个字符串的所有前缀的出现次数的和。 思路：这道题需要完全理解 nxt 函数是干嘛的。nxt[i] 表示的是字符串的 0..i-1 位中，前缀和后缀相等的串的最长长度为 nxt[i]。

hdu 2594 题目链接 题意：given string s1,s2, find the longest prefix of s1 that is a suffix of s2. 思路：kmp。。。懒得说了。注意边界。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 01时12分51秒 4File Name :code/hdu/2594.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=5E5+7; 34char a[N],b[N]; 35int nxt[N]; 36void getnxt( char *s) 37{ 38 int n = strlen(s); 39 int i = 0 ; 40 int j = -1; 41 nxt[0] = -1; 42 while (i<n) 43 if (j==-1||s[i]==s[j]) nxt[++i]=++j; 44 else j = nxt[j]; 45} 46int kmp(char *a,char *b) 47{ 48 int n = strlen(a); 49 int m = strlen(b); 50 getnxt(b); 51 int i = 0; 52 int j = 0; 53 while (i<n) 54 { 55 if (j==-1||a[i]==b[j]) i++,j++; 56 else j = nxt[j]; 57 } 58 if (i==n) return j; 59 return 0; 60} 61int main() 62{ 63 #ifndef ONLINE_JUDGE 64 freopen("code/in.txt","r",stdin); 65 #endif 66 while (~scanf("%s %s",a,b)) 67 { 68// cout<<"a:"<<a<<" b:"<<b<<endl; 69 int k = kmp(b,a); 70 if (k==0) 71 puts("0"); 72 else printf("%s %d\n",b+(strlen(b)-k),k); 73 74 ms(a,0); 75 ms(b,0); 76 } 77 #ifndef ONLINE_JUDGE 78 fclose(stdin); 79 #endif 80 return 0; 81}

hdu 2203 题目链接 题意：给定字符串A（一个环），和字符串B，问B是否在A中出现过。 思路：环的问题。。复制一遍到末尾就好了。。出于严谨的考虑。。我们只复制n-1个字符。 以及要记得判断文本串的长度是否大于等于模板串，如果小于，直接判断no//然而题目数据太水，没判也过了

hdu 3746题目链接 题意：给定一个字符串，是一个环（首尾相连），问至少再添加多少个珠子才能使得整个串是循环的。。。 思路：一下子想到了最小覆盖子串的模型。。。我求出最小覆盖子串的长度（n-nxt[n]）。然后特判下最小覆盖子串的长度等于字符串长度的情况。。。试着叫了一发。。。竟然就A了2333.。。大概是所谓的题感吧（逃

hdu 5763 题目链接 题意：给定两个字符串A和B，每个出现在A中的B(可以overlap)都有两种含义，问A串一共可能有多少种含义。 思路：kmp+dp. 考虑dp[i]为前i个字符（也就是从开始长度为i，注意不是字符串的下标为i）的含义数。

hdu 1867 题意 题意：给两个字符串，将两个字符串首尾拼接之后得到一个长度最短的字符串，求这个最短的字符串（一个串的前缀可能是另一个串的后缀，这样的话只出现一次就行了） 思路：kmp。。注意和hdu 1841区分。那道题是只要得到一个串包含两个串即可。这道题是首尾拼接得到。

hdu 1841题目链接 题意：给两个字符串，问包含这两个字符串的最小的字符串的长度（最小是因为，一个串的子串可能是另一个串的后缀，这样出现一次就可以了） 思路：其实这道题最关键的思想部分是和kmp没有关系的。。。

hdu 1358 题目链接 题意：给一个字符串，求这个字符串的每个前缀（包括本身）的能否由k个子串组成（K>1） 思路：和poj 2406 比较类似。。 结论：字符编号从0开始，如果又i%(i-next[i])==0，则i前面的 串为一个轮回串，其中轮回子串出现i/(i-next[i])次。

hdu 2087 题目链接 题意：问模式串在文本串中出现的次数，不允许重叠。 思路：kmp，关键在于不允许重叠。。。 其实只要每次找到的时候j=0一下就好咯。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月11日 星期四 02时52分44秒 4File Name :code/hdu/2087.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=1E3+7; 36char a[N],b[N]; 37int nxt[N]; 38 39void getnxt(char *s) 40{ 41 int i = 0; 42 int j = -1; 43 nxt[0] = -1; 44 int n = strlen(s); 45 while (i<n) 46 if (j==-1||s[i]==s[j]) nxt[++i]=++j; 47 else j = nxt[j]; 48} 49int kmp(char *a,char *b) 50{ 51 int n = strlen(a); 52 int m = strlen(b); 53 getnxt(b); 54 int i = 0; 55 int j = 0; 56 int cnt = 0 ; 57 while (i<n) 58 { 59 if (j==-1||a[i]==b[j]) i++,j++; 60 else j=nxt[j]; 61 if (j==m) 62 { 63 cnt++; 64 j=0; //不允许重叠 65 } 66 } 67 return cnt; 68 69} 70int main() 71{ 72 #ifndef ONLINE_JUDGE 73 freopen("code/in.txt","r",stdin); 74 #endif 75 76 while (~scanf("%s",a)) 77 { 78 if (a[0]=='#') break; 79 scanf("%s",b); 80 int ans = kmp(a,b); 81 printf("%d\n",ans); 82 } 83 84 #ifndef ONLINE_JUDGE 85 fclose(stdin); 86 #endif 87 return 0; 88}

hdu 1711 题目链接 题意：给定两个数列，问第二个数列在第一个数列中出现的位置（第一个元素对应的位置） 思路：数列也可以看成字符串，然后左kmp，返回的答案是i+1-m。。。1A

poj 3080 题目链接 题意：给出n个字符串（n<=10），字符串长度不超过70，问出现在全部n个字符串中的最长并且字典序最小的长度大于等于3的子串。 思路：数据范围很小。。。直接暴力枚举+kmp匹配一下。。。

poj 2185 题目链接 题意：给出一个字符矩形，问一个面积最小的矩形，覆盖掉整个矩形。大概就是二维的最小覆盖子串。 思路：对于每一行做最小覆盖子串，然后求lcm，每一列也是如此。最后记得判断不能超过原有的n,m。

参考资料（本文大部分是参考这篇博客，附带一些证明步骤的解释） 首先明确一些概念： 最小覆盖子串：对于某个字符串s，它的最小覆盖子串指的是长度最小的子串p，p满足通过自身的多次连接得到q，最后能够使s成为q的子串。 比如： 对于s=“abcab”，它的最小覆盖子串p=“abc”，因为p通过在它后面再接上一个p（即重叠0个字符），可以得到q=“abcabc”，此时s是q的子串。 对于s=“ababab”，它的最小覆盖子串为p=“ab”。

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 为什么你们都那么强啊，看几个小时就看懂了……

题目链接 傻逼模拟。。读完题就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}