【題目鏈接】

OpenJudge NOI 1.7 30:字符環(huán)

【題目考點】

1. 字符串

2. 環(huán)形數(shù)組遍歷

環(huán)形數(shù)組元素個數(shù)為n，下標為0~n-1，在環(huán)形數(shù)組中下標i取下一個位置的方法:i = (i + 1) % n
環(huán)形數(shù)組中下標i后第j個位置的下標為：(i + j) % n

3. 環(huán)形數(shù)組轉(zhuǎn)一維數(shù)組

一個環(huán)形數(shù)組有n個元素。如想遍歷該環(huán)形數(shù)組，同時取一段子數(shù)組做某種運算，而該子數(shù)組的長度小于等于2n，那么就可以將該環(huán)形數(shù)組變?yōu)橐粋€長為2n的一維數(shù)組，將環(huán)形數(shù)組中的元素在一維數(shù)組上排列兩遍，而后在該一維數(shù)組上做遍歷。

例：在環(huán)形數(shù)組上找最大子段和
假設(shè)環(huán)形數(shù)組為：4 -4 2 -3 5 -3
轉(zhuǎn)為一維數(shù)組：4 -4 2 -3 5 -3 4 -4 2 -3 5 -3
其最大子段和為5-3+4=6

【解題思路】

解法1：在環(huán)形數(shù)組上遍歷

輸入兩個字符串到s1和s2，其長度分別為l1、l2。i1與i2分別為s1與s2的下標，i1從0遍歷到l1-1， i2從0遍歷到l2-1。對于每對i1, i2，看s1從i1開始，與s2從i2開始，相同的子串最長可以是多長。在這一過程中，需要使用在環(huán)形數(shù)組中取下一個位置的寫法，即形如i = (i + 1) % n的寫法。對每次取到的子串長度取最大值，即為結(jié)果。

解法2：環(huán)形數(shù)組轉(zhuǎn)為一維數(shù)組

將兩個環(huán)形字符串轉(zhuǎn)為一維字符串（方法見題目考點3），而后就是兩個一般字符串找最長公共子串的問題了，做法與解法1相似，遍歷時下標直接加1即可。

【題解代碼】

解法1：在環(huán)形數(shù)組上遍歷

#include<bits/stdc++.h> using namespace std; #define N 260 int main() {char s1[N], s2[N];int i1 = 0, i2 = 0, l1, l2, mxLen = 0;//i1, i2分別是s1, s2的下標 mxLen:最大公共子串長度 cin >> s1 >> s2;l1 = strlen(s1);l2 = strlen(s2);for(int i1 = 0; i1 < l1; ++i1)for(int i2 = 0; i2 < l2; ++i2){int j = 0;//j為公共子串長度，最長也就是l1和l2的較小值 while(j < l1 && j < l2){if(s1[(i1+j)%l1] == s2[(i2+j)%l2])//在環(huán)形數(shù)組s1中i1后第j個元素下標為(i1+j)%l1，s2中i2后第j個元素下標為(i2+j)%l2 j++;elsebreak;}mxLen = max(mxLen, j);}cout << mxLen;return 0; }

解法2：環(huán)形數(shù)組轉(zhuǎn)為一維數(shù)組

#include<bits/stdc++.h> using namespace std; #define N 260 void doubleArr(char s[])//將s變?yōu)樵瓉淼膕重復(fù)2遍 如將abc變?yōu)閍bcabc {int len = strlen(s);for(int i = 0; i <= len; ++i)s[i+len] = s[i]; } int main() {char s1[N], s2[N];int i1 = 0, i2 = 0, l1, l2, mxLen = 0;//i1, i2分別是s1, s2的下標 mxLen:最大公共子串長度 cin >> s1 >> s2;l1 = strlen(s1);l2 = strlen(s2);doubleArr(s1);//將字符串變?yōu)樵址貜?fù)2遍，即為用一維數(shù)組表示環(huán)形數(shù)組 doubleArr(s2);for(int i1 = 0; i1 < l1; ++i1)for(int i2 = 0; i2 < l2; ++i2){int j = 0;//j為公共子串長度，最長也就是l1和l2的較小值 while(j < l1 && j < l2){if(s1[i1+j] == s2[i2+j])j++;elsebreak;}mxLen = max(mxLen, j);}cout << mxLen;return 0; }

總結(jié)

以上是生活随笔為你收集整理的OpenJudge NOI 1.7 30:字符环的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。