【題目鏈接】

OpenJudge NOI 1.7 26:字符串最大跨距

【題目考點】

1. 字符串

2. string類

string s, s1;

• s.find(s1):查找s1在s中第一次出現的位置（從左至右查找），如不存在，返回string::npos。
• s.rfind(s1):查找s1在s最后一次出現的位置（從右至左查找），如不存在，返回string::npos。
• s.substr(pos, len): 從下標pos起截取長度為len 的字符串

【解題思路】

解法1：使用字符數組

先讀入整個字符串，遍歷字符串，通過逗號將整個字符串拆分為s, s1, s2三個字符串。
讀到第一個逗號時，將該數組元素改為’\0’，那么該字符串就是題目中說的字符串s。
繼續向后遍歷，遍歷到的字符向s1做數組填充，讀到第二個逗號時停止。s1末尾添加’\0’。
繼續向后遍歷到’\0’，將遍歷到的字符填充到s2。至此完成s,s1,s2三個字符串的構造。
以下類似找子串的方法。

從前向后遍歷s，看有沒有一段字符與s1相同。方法為給s1也設一個下標i1，如果看到相同字符，i1增加。如果不同，i1變為0。如果i1已經等于s1的長度，那么說明s中包含s1，跳出循環。此時i指向的是s1在s中最后一個字符的后一個位置，如果s中不存在s1，那么i為s的長度l。最后i的值記為a。

從后向前遍歷s，對s2也從后向前遍歷，看s中是否存在s2，方法與上面類似。如果s中包含s2，i指向s2在s中第一個字符的前一個位置，如果s中不包含s2，i的值為-1。最后i的值記為b。

從s1的后一個字符a到s2的前一個字符b，包括a和b，這段字符的個數即為字符串的跨度。其長度為b-a+1。如果二者重疊，或其中有一個不存在b-a+1一定是負數。

解法2：使用string類

輸入s，遍歷s，找到兩個逗號的下標c1，c2。
s1為從c1+1位置開始，長度為c2-(c1+1)
s2為從c2+1位置開始，到s的末尾
最后修改s，為從第0位置開始，長度為c1。
使用成員函數find()在s中查找子串s1，使用rfind()在s中查找s2。如果二者存在，即可確定s1的最后一個字符和s2第一個字符的位置，而后求出s1到s2的跨度。

【題解代碼】

解法1：使用字符數組

#include <bits/stdc++.h> using namespace std; int main() {char s[355], s1[15], s2[15];cin >> s;//先把整個字符串讀入s int l, l1 = 0, l2 = 0, i, i1, i2, a, b;//l,l1,l2:s,s1,s2的長度 i,i1,i2:s,s1,s2的下標 for(i = 0; s[i] != ',' ; ++i);s[i] = '\0';//去掉第一個逗號后面的字符 l = i;//更新s的長度 i++;while(s[i] != ',')//構造s1 s1[l1++] = s[i++];s1[l1] = '\0';i++;while(s[i] != '\0')//構造s2s2[l2++] = s[i++];s2[l2] = '\0'; i = i1 = 0;while(i < l){if(s[i] == s1[i1]){i++;i1++;if(i1 == l1)break;}else if(i1 > 0)//如果i1大于0，那么把i1指向第0位置，再做比較 i1 = 0;else//如果i1已經為0 s[i]與s1[i1]還是不同，那么看后面的字符 i++;}a = i;//此時i指向s1最后一個字符在s中的后一個位置。如果s中不存在s1，該值為l i = l - 1;//i與i2都指向字符串最后一個字符 i2 = l2 - 1;while(i >= 0){if(s[i] == s2[i2]){i--;i2--;if(i2 < 0)break;}else if(i2 != l2 - 1)i2 = l2 - 1;elsei--;}b = i;//此時i指向s2第0個字符在s中的前一個位置。如果不存在s2，該值為-1 //此時，s1和s2間的字符為下標a到b（包括a和b） if(b - a + 1 >= 0)cout << b - a + 1;elsecout << -1;return 0; }

解法2：使用string類

#include <bits/stdc++.h> using namespace std; int main() {string s, s1, s2;int i, c1, c2, a, b;//c1,c2:第一個逗號和第二個逗號的下標 cin >> s;//先把整個字符串讀入s for(i = 0; s[i] != ','; ++i);c1 = i;for(i = c1 + 1; s[i] != ','; ++i);c2 = i;s1 = s.substr(c1 + 1, c2 - c1 - 1);s2 = s.substr(c2 + 1);//從c2+1到末尾s = s.substr(0, c1);a = s.find(s1);//a為s1在s中第一次出現時第一個字符在s中的位置。 b = s.rfind(s2);//b為s2在s中最后一次出現時第一個字符在s中的位置。if(a == string::npos || b == string::npos)//如果s1或s2不存在 {cout << -1;return 0;}a = a + s1.length();//a指向s1最后一個字符的后一個位置if(b - a >= 0)cout << b - a;elsecout << -1;return 0; }

總結

以上是生活随笔為你收集整理的OpenJudge NOI 1.7 26:字符串最大跨距的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。