c語(yǔ)言字符串編程練習(xí)題

1、1.題意：找出原串中出現(xiàn)超過(guò)2次的子串的數(shù)目，每個(gè)子串出現(xiàn)多次時(shí)不可重疊。分析：枚舉子串的長(zhǎng)度len，找到滿(mǎn)足連續(xù)的heighti=len的最左端 l 和最右端的位置 r，如果r-l=len說(shuō)明子串沒(méi)有重疊。#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. 題意：給出長(zhǎng)度為n的數(shù)字序列,求重復(fù)出現(xiàn)次數(shù)不小于k的最長(zhǎng)序列(連續(xù))的長(zhǎng)度。例如序列 1 2 3 2 3 2 3 1，k=2，那么序列2 3 2 3重復(fù)出現(xiàn)了兩次，長(zhǎng)度為4。分析：二分枚舉長(zhǎng)度，如果在height數(shù)

5、組中連續(xù)出現(xiàn)超過(guò)k次的話就滿(mǎn)足。#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下標(biāo)就是從1開(kāi)始了 getheight(); solve(k); return 0;3. 題意：Gardon是個(gè)怕麻煩的人（恩，就是愛(ài)偷懶的人），很顯然將64個(gè)圓盤(pán)逐一搬動(dòng)直到所有的

9、盤(pán)子都到達(dá)第三個(gè)柱子上很困難，所以Gardon決定作個(gè)小弊，他又找來(lái)了一根一模一樣的柱子，通過(guò)這個(gè)柱子來(lái)更快的把所有的盤(pán)子移到第三個(gè)柱子上。下面的問(wèn)題就是：當(dāng)Gardon在一次游戲中使用了N個(gè)盤(pán)子時(shí)，他需要多少次移動(dòng)才能把他們都移到第三個(gè)柱子上？很顯然，在沒(méi)有第四個(gè)柱子時(shí)，問(wèn)題的解是2N-1，但現(xiàn)在有了這個(gè)柱子的幫助，又該是多少呢？分析：先將A柱子上的k個(gè)盤(pán)子通過(guò)四個(gè)柱子移動(dòng)的D柱子上，在將剩下的n-k盤(pán)子通過(guò)三個(gè)柱子移動(dòng)到C柱子上，在將D柱上的盤(pán)子通過(guò)四個(gè)柱子移動(dòng)到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