每日算法刷题Day10-字符串最大跨距、最长公共字符串后缀

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

31.字符串最大跨距

有三个字符串 S,S1,S2，其中，S 长度不超过 300，S1 和 S2的长度不超过 10。

现在，我们想要检测 S1 和 S2 是否同时在 SS 中出现，且 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 存在，则输出 −1。

输入样例：

abcd123ab888efghij45ef67kl,ab,ef

输出样例：

18

思路

分别两次匹配字符串，s1从左向右匹配，s2从右向左匹配。再根据情况分别判断即可。重点在练，多敲几遍。

#include<bits/stdc++.h>
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;
    if(s.size()<s1.size() || s.size() < s2.size())puts("-1");
    else{
    
    int l = 0;
    for(;l + s1.size() <= s.size();l++)
    {
        int k = 0;
        for(; k < s1.size();k++)
        {
            if(s[l + k] != s1[k])break;
        }
        if( k == s1.size())break;
    }
    
    //s2从右向左找
    int r = s.size() - s2.size();
    for(; r >= 0 ;r--)
    {
        int k = 0;
        for(; k < s2.size();k++)
        {
            if(s[r+ k] != s2[k])break;
        }
        if( k == s2.size())break;
    }
    
    l += s1.size() - 1;
    
    if(l >= r)puts("-1");
    else printf("%d\n", r - l - 1);
    return 0;
    }
}

32.最长公共字符串后缀

给出若干个字符串，输出这些字符串的最长公共后缀。

输入格式

由若干组输入组成。

每组输入的第一行是一个整数 N。

N 为 0 时表示输入结束，否则后面会继续有 N 行输入，每行是一个字符串（字符串内不含空白符）。

每个字符串的长度不超过 200。

输出格式

共一行，为 N 个字符串的最长公共后缀（可能为空）。

数据范围

1≤N≤200

输入样例：

3
baba
aba
cba
2
aa
cc
2
aa
a
0

输出样例：

ba

a

思路

伪代码如下

for( 枚举后缀长度)
	for(所有字符串)
		for(枚举str[0]与str[i]的n个字符)

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 200;

int n;
string str[N];

int main()
{
    while(cin >> n, n)
    {
        int len = 1000;
        for(int i = 0; i < n; i++)
        {
            cin >> str[i];
            if(str[i].size() < len)len = str[i].size();
        }
        
        for(;len;len--)
        {
            
            bool success = true;
            for(int i = 0; i < n; i++)
            {
                bool is_same = true;
                for(int j = 1; j <= len ; j++)
                {
                    if( str[0][str[0].size() - j ] != str[i][str[i].size()- j])
                    {
                        is_same = false;
                        break;
                    }
                }
                if(!is_same)
                {
                    success = false;
                    break;
                }
                
            }
            if(success)break;
        }
        
        cout << str[0].substr(str[0].size() - len )<<endl;
        
    }
    return 0;
}