c语言字符串编程练习题

1、1.题意：找出原串中出现超过2次的子串的数目，每个子串出现多次时不可重叠。分析：枚举子串的长度len，找到满足连续的heighti=len的最左端 l 和最右端的位置 r，如果r-l=len说明子串没有重叠。#include #include #include using namespace std;const int maxn = 1005;int N;char smaxn;int samaxn,tmaxn,t2maxn,cmaxn;void suffix_sa(int n, int m) int i, *x=t, *y=t2; for (i=0; im; i+) ci = 0; for (

2、i=0; in; i+) cxi=si+; for (i=0; i=0; i-) sa-cxi = i; for (int k=1; k=n; k=1) int p = 0; for (i=n-k; in; i+) yp+ = i; for (i=0; i= k) yp+ = sai-k; for (i=0; im; i+) ci = 0; for (i=0; in; i+) cxyi+; for (i=0; i=0; i-) sa-cxyi = yi; swap(x,y); p = 1; xsa0 = 0; for (i=1; i=n) break; m = p; int rankmaxn,

3、heightmaxn;void getheight() int i, j, k=0; for (i=1; i=N; i+) ranksai = i; for (i=0; iN; i+) if (k) k-; int j = saranki-1; while (si+k = sj+k) k+; heightranki = k; void solve() N = strlen(s); suffix_sa(N+1,z+1); getheight(); int res = 0; int i, j, k, l, r; for (i=1; iN/2+1; i+) l = N,r = -1; for (j=

4、2; j=i) r = max(r,max(saj-1,saj); l = min(l,min(saj-1,saj); else if (heightj=i) res+; r = -1; l = N; if (r-l=i) res+; printf(%dn,res);int main() while (scanf(%s,s),s0!=#) solve(); return 0;2. 题意：给出长度为n的数字序列,求重复出现次数不小于k的最长序列(连续)的长度。例如序列 1 2 3 2 3 2 3 1，k=2，那么序列2 3 2 3重复出现了两次，长度为4。分析：二分枚举长度，如果在height数

5、组中连续出现超过k次的话就满足。#include #include #include using namespace std;const int maxn = 1000002;int smaxn;int samaxn,tmaxn,t2maxn,cmaxn;int N;void build_sa(int n,int m) int i, *x=t, *y=t2; for (i=0; im; i+) ci = 0; for (i=0; in; i+) cxi = si+; for (i=1; i=0; i-) sa-cxi = i; int p; for (int k=1; k=n; k=1) p

6、= 0; for (i=n-k; in; i+) yp+ = i; for (i=0; i= k) yp+ = sai-k; for (i=0; im; i+) ci = 0; for (i=0; in; i+) cxyi+; for (i=0; i=0; i-) sa-cxyi = yi; swap(x, y); p = 1; xsa0 = 0; for (i=1; i= n) break; m = p; int rankmaxn,heightmaxn;void getheight() int i, j, k = 0; for (i=1; i=N; i+) ranksai = i; for

7、(i=0; iN; i+) if (k) k-; int j = saranki-1; while (si+k = sj+k) k+; heightranki = k; bool ok(int len, int k) int i; int tot = 1; for (i=1; i= len) tot+; if (tot = k) return true; else tot = 1; return false;void solve(int k) int i, j; int l, r, mid, res; l = k; r = N; while (l = r) mid = (l+r)/2; if

8、(ok(mid, k) res = mid; l = mid+1; else r = mid-1; printf(%dn,res);int main() / freopen(in.in,r,stdin); int k, i; while (scanf(%d %d,&N,&k)!=EOF) for (i=0; iN; i+) scanf(%d, &si); build_sa(N+1,20001);/ N+1之后，sa下标就是从1开始了 getheight(); solve(k); return 0;3. 题意：Gardon是个怕麻烦的人（恩，就是爱偷懒的人），很显然将64个圆盘逐一搬动直到所有的

9、盘子都到达第三个柱子上很困难，所以Gardon决定作个小弊，他又找来了一根一模一样的柱子，通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是：当Gardon在一次游戏中使用了N个盘子时，他需要多少次移动才能把他们都移到第三个柱子上？很显然，在没有第四个柱子时，问题的解是2N-1，但现在有了这个柱子的帮助，又该是多少呢？分析：先将A柱子上的k个盘子通过四个柱子移动的D柱子上，在将剩下的n-k盘子通过三个柱子移动到C柱子上，在将D柱上的盘子通过四个柱子移动到C柱子上。 dpi = min(2*dpk+an-k)#include #include #include using name

10、space std;long long d66 = 0,1,3;long long a66;int main() int i, j, n; d64 = 18433; for (i=1; i=63; i+) ai = (1LLi)-1; for (i=2; i=63; i+) di = 2*d1+ai-1; for (j=2; ji; j+) di = min(di,2*dj+ai-j); while (scanf(%d,&n)!=EOF) printf(%lldn,dn); return 0;代码模版startstart1234567891011121314151617181920212223

11、242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481

12、49150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223#define _CRT_SECURE_NO_DEPRECATE#include #include #include #include #include

13、 #include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, /STACK:266777216)usingnamespacestd;#define pb push_back#define ppb pop_back#define pi 3.1415926535897932384626433832795028841971#define mp make_pair#define x first#def

14、ine y second#define pii pair#define pdd pair#define INF 1000000000#define FOR(i,a,b) for (int _n(b), i(a); i =_b;i-)#define all(c) (c).begin(), (c).end()#define SORT(c) sort(all(c)#define rep(i,n) FOR(i,1,(n)#define rept(i,n) FOR(i,0,(n)-1)#define L(s) (int)(s).size()#define C(a) memset(a),0,sizeof(

15、a)#define VI vector #define ll long longconstintdi = 0, 1, 0, -1 ;constintdj = 1, 0, -1, 0 ;inta, b, c, d, n, m, k;charmas20022002;intcs20022002, cs2420022002;inthor20022002, ver20022002;boolused20022002;pii sof4;pii q4000002;voidbfs(intbi,intbj)inta = 0, b = 0;qb+ = mp(bi, bj);usedbibj = 1;while(a

16、b)intci = qa.x;intcj = qa+.y;sof0 = min(sof0, pii(ci, cj);sof1 = min(sof1, pii(cj, ci);sof2 = min(sof2, pii(-ci, -cj);sof3 = min(sof3, pii(-cj, -ci);rept(i, 4)intni = ci + dii;intnj = cj + dji;if(ni = n | nj = m)continue;if(usedninj | masninj != mascicj)continue;usedninj = 1;qb+ = mp(ni, nj);inlinei

17、ntsum(intx,inty)if(x 0 | y 0)return0;returncsxy;inlineintsum(intx1,inty1,intx2,inty2)returnsum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);inlineintsum2(intt,intx,inty)if(x 0 | y 2)return0;if(cnt = 1)if(sum2(0, r1 + 1, c1 + 1, r2 - 1, c2 - 1) = 1)return2;elsereturn0;rept(i, 4)i

18、f(!sum2(i, r1 + 1, c1 + 1, r2 - 1, c2 - 1)return2;return0;voidinit() memset(cs, 0,sizeof(cs);memset(cs2, 0,sizeof(cs2);memset(hor, 0,sizeof(hor);memset(ver, 0,sizeof(ver);memset(used, 0,sizeof(used);a = b = c = d = n = m = k = 0;intmain()/freopen(data.in, r, stdin);/freopen(output.txt, w, stdout);while(gets(mas0)init();sscanf(mas0,%d%d, &n, &m);rept(i, n)gets(masi);rept(j, m)csij = masij -0;if(!i & !j);elseif(!j) csij += csi - 1j;elseif(!i) csij += csij - 1;elsecsij += csi - 1j + csij - 1 - csi - 1j - 1;rept(i, n)rept(j, m)ho