字符串基础题系列题解

字符串最大跨距

点击查看

有三个字符串 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 存在，则输出 −1。

输入样例：
abcd123ab888efghij45ef67kl,ab,ef
输出样例：
18

//法一：模拟
#include <iostream>

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");
        return 0;
    }
    
    int l = 0;//定义l指针，指向s1的起始点
    while(l + s1.size() <= s.size()){
        int k = 0;//定义k指针，用来判断扫描的子串是否等于s1
        while(k < s1.size()){
            if(s[k + l] != s1[k]) break;//如果已经不相等了，那就break
            k++;
        }
        if(k == s1.size()) break;
        l ++;
    }
    
    int r = s.size() - s2.size();
    while(r >= 0){
        int k = 0;
        while(k < s2.size()){
            if(s[r + k] != s2[k]) break;
            k++;
        }
        if(k == s2.size()) break;
        r--;
    }
    
    if(r > l + s1.size() - 1 && r > 0 && l + s1.size() < s.size()){
        cout << r - l - s1.size() << endl;
    }
    else puts("-1");
    
    return 0;
}

//法二：STL
#include <iostream>
using namespace std;
int main(){
    
    char ch;
    string s, a, b;
    
    getline(cin, s, ',');
    getline(cin, a, ',');
    getline(cin, b, '\n');
    
    int x = s.find(a);
    int y = s.rfind(b);
    
    if(x != string::npos && y != string::npos && x + a.size() - 1 < y){
        cout << y - x - a.size() << endl;
    }
    
    else cout << "-1" << endl;
    return 0;
}

字符串乘方

点击查看

给定两个字符串 a 和 b，我们定义 a×b 为他们的连接。

例如，如果 a=abc 而 b=def， 则 a×b=abcdef。

如果我们将连接考虑成乘法，一个非负整数的乘方将用一种通常的方式定义：a0=``(空字符串)，a(n+1)=a×(an)。

输入格式
输入包含多组测试样例，每组测试样例占一行。

每组样例包含一个字符串 s，s 的长度不超过 100。

最后的测试样例后面将是一个点号作为一行。

输出格式
对于每一个 s，你需要输出最大的 n，使得存在一个字符串 a，让 s=an。

输入样例：
abcd
aaaa
ababab
.
输出样例：
1
4
3

#include <iostream>

using namespace std;

int main(){
    
    string a;
    
    while(cin >> a, a != "."){
        int len = a.size();
        
        for(int n = len; n; --n){
            if(len % n == 0){
                int m = len / n;
                string s = a.substr(0, m);
                string str;
                for(int i = 0; i < n; ++i){
                    str += s;
                }
                if(str == a){
                    cout << n << endl;
                    break;
                }
            }
        }
    }
    return 0;
    
}

字符串移位包含问题

点击查看

对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串 s1 和 s2，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。

例如 CDAA 是由 AABCD 两次移位后产生的新串 BCDAA 的子串，而 ABCD 与 ACBD 则不能通过多次移位来得到其中一个字符串是新串的子串。

输入格式
共一行，包含两个字符串，中间由单个空格隔开。

字符串只包含字母和数字，长度不超过 30。

输出格式
如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串，则输出 true，否则输出 false。

输入样例：
AABCD CDAA
输出样例：
true

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    string a, b;
    string c;
    
    cin >> a >> b;
    
    if(a.size() < b.size()) swap(a, b);
    
    for(int i = 0; i < a.size(); ++i){
        a = a.substr(1) + a[0];
        for(int j = 0; j + b.size() <= a.size(); ++j){
            int k = 0;
            for(; k < b.size(); ++k)
                if(a[j + k] != b[k]) break;
               
            if(k == b.size()){
                puts("true");
                return 0;
            }
        }
    }
    puts("false");
    
    return 0;
}

最长公共字符串后缀

点击查看

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

输入格式
由若干组输入组成。

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

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

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

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

数据范围
1≤N≤200
输入样例：
3
baba
aba
cba
2
aa
cc
2
aa
a
0
输出样例：
ba

a

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210;

string str[N];

int main(){
	int n;
	
	while(cin >> n, n){
		
		int len = 200;
		for(int i = 0; i < n; ++i){
			cin >> str[i];
			if(str[i].size() < len) len = str[i].size();
		}
		
		while(len){
			bool success = true;
			for(int i = 1; i < n; ++i){//遍历除第0个字符串外的字符串 
				bool isSame = true;
				for(int j = 1; j <= len; ++j){//遍历每个字符串的后缀 
					if(str[0][str[0].size() - j] != str[i][str[i].size() - j]){
						isSame = false;
						break;
					}
				}
				if(!isSame){
					success = false;
					break;
				}
			}
			if(success) break;
			len --;
		}
		cout << str[0].substr(str[0].size() - len) << endl;
	}
	return 0;
}