778. 字元串最大跨距

文章目錄

• ​​Question​​
• ​​Ideas​​
• ​​Code​​

Question

有三個字元串 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，字元串之間用逗号隔開。

資料保證三個字元串中不含空格和逗号。

輸出格式

輸出一個整數，表示最大跨距。

Ideas

1. 查找兩個字串（s1、s2）的位置
2. 判斷s1、s2位置是否有交集
3. 輸出s1、s2之間的位置差

Code

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s, s1, s2;
    char c;
    while (cin >> c, c != ',') s += c;
    while (cin >> c, c != ',') s1 += c;
    while (cin >> c) s2 += c;
    
    // s不包括s1和s2
    if (s1.size() > s.size() || s2.size() > s.size())
        cout << -1 << endl;
    else
    {
        // 确定s1、s2的位置，均從起點開始
        int l = 0;
        for (; l + s1.size() <= s.size(); l++)
        {
            int k = 0;
            for (; k < s1.size(); k++)
            {
                if (s1[k] != s[l+k]) break;
            }
            if (k == s1.size()) break;
        }
        
        int r = s.size() - s2.size();
        for (; r; r--)
        {
            int k = 0;
            for (; k < s2.size(); k++)
            {
                if (s2[k] != s[r+k]) break;
            }
            if (k == s2.size()) break;
        }
        
        l = l + s1.size() - 1;
        
        if (l >= r) puts("-1");
        else printf("%d\n", r-l-1);
    }
    
        
    return 0;
}