字符串最大跨距

大家好，我是讯享网，很高兴认识大家。

题目描述：

有三个字符串 S，S1, S2，其中，S长度不超过300，S1 和 S2 的长度不超过10。想检测S1和S2 是否同时在 S中出现，且S1位于S2 的左边，并在 S 中互不交叉（即，S1 的右边界点在S2 的左边界点的左侧)。计算满足上述条件的最大跨距（即，最大间隔距离：最右边的S2 的起始点与最左边的 S1 的终止点之间的字符数目）。如果没有满足条件的S1,S2 存在，则输出−1。

例如，S="abcd123ab888efghij45ef67kl"，S1="ab"，S2="ef"。其中，S1 在 S 中出现了 2 次，S2 也在 S 中出现了 2 次，最大跨距为18。

输入格式：

三个串：S,S1,S2，其间以逗号间隔（注意，S1,S2,S3 中均不含逗号和空格）；

输出格式：

S1 和 S2 在 S 最大跨距；若在 S 中没有满足条件的 S1 和 S2，则输出 −1。

注意：（1）S1和S2在S中不能交叉

（2）求的是最大跨距

讯享网

另：（1）ch数组存的是输入的全部字符，即S,S1和S2都包含在内；a记录ch中字符个数

（2）m和n记录两个逗号的下标，方便分离出字符串S1和S2；t记录S1中字符个数，l记录S2中字符个数

（3）因为找的是S1和S2的最大跨距，所以找S1是顺序查找，找S2时逆着查找，一但找到满足条件的S1，S2就直接跳出循环

（4）b数组和c数组的作用一样。以查找满足条件的S1为例：因为查找是一个字符一个字符进行的，如果按顺序查找到一个s[i]满足是s[i]=s1[0]（如果不存在s[i]=s1[0],说明s中不存在s1）；接着把这个s[i]连同s[i]后面几个字符一同存储到b数组中（存储后b数组中的字符个数应与s1中字符个数一样）；然后比较b数组和s1数组是否一样，如果一样就跳出循环（反之，则继续进行下一次循环）。查找s2和查找s1的思路基本一致

（5）p和q是为了标记出是否找出满足条件的S1和S2。p和q的初值均为0，找出满足条件的S1后，p的值变为1；同理，找出满足条件的S2后，q的值也变为1

（6）d记录满足条件（s[i]=s1[0]且字符串b和s1相同）时i的值；e记录满足条件（s[i]=s2[l-1]且字符串c和s2相同）时i的值

代码：

#include <stdio.h> #include <string.h> char s[310], s1[310], s2[310], ch[710], b[310], c[310]; int q = 0, p = 0; int main() {     int d, e;     gets(ch);     int a = strlen(ch);     int m, n, t = 0, l = 0;     for (int i = 0; i < a; i++) {         if (ch[i] == ',') {             m = i;             break;         } else             s[i] = ch[i];     }//分离出字符串S     for (int i = m + 1; i < a; i++) {         if (ch[i] == ',') {             n = i;             break;         } else             s1[t++] = ch[i];     }//分离出字符串S1     for (int i = n + 1; i < a; i++) {         s2[l++] = ch[i];     }//分离出字符串S2     for (int i = 0; i < m; i++) {//m是第一个逗号的下标         if (s[i] == s1[0]) {             for (int j = 0; j < t; j++) {                 b[j] = s[i];                 i++;             }             i = i - t;//不能漏掉             if ((strcmp(b, s1)) == 0) {                 p = 1;                 d = i;                 break;             }         }         if (p == 1)             break;     }//查找S1     for (int i = m - 1; i >= d + t; i--) {         if (s[i] == s2[l - 1]) {             for (int j = l - 1; j >= 0; j--) {                 c[j] = s[i];                 i--;             }             if (i >= d + t - 1)//防止查找到的S1和S2交叉                 i = i + l;//不能漏掉             else {                 break;             }//查找S2是逆序进行的,如果第一个查找出来的就交叉了，后面肯定也会交叉             if ((strcmp(c, s2)) == 0) {                 q = 1;                 e = i;                 break;             }         }         if (q == 1)             break;     }     if (p == 1 && q == 1) {//p和q都为1，表明查找出了满足条件的S2和S1         int u = e - d - 1 - t + 1 - l + 1;         printf("%d", u);     } else         printf("-1");     return 0; }

讯享网

法二：

讯享网#include<iostream> #include<algorithm> #include<string.h> #include<string> using namespace std; int main() { string s,s1,s2; getline(cin,s,','); getline(cin,s1,','); getline(cin,s2); if(s.find(s1)==string::npos||s.find(s2)==string::npos) cout<<-1<<endl; else { int l1=s.find(s1),r1=l1+s1.length()-1; reverse(s.begin(),s.end()); reverse(s2.begin(),s2.end()); int r2=s.length()-s.find(s2)-1; int l2=r2-s2.length()+1; if(l2<=r1) cout<<-1<<endl; else cout<<l2-r1-1<<endl; } return 0; }

写的不太好，代码有点长，变量有点多，如果出现问题，欢迎指正呀

相关推荐