题解 P13307 域名判断

Part 1 理解题意

这道题的题意是在不看大小写的情况下从头开始到一个位置结束的子串中，求出所有的教育网站域名。具体要求去看题目，讲得很清晰。

然后输出所有满足条件的右端点。

Part 2 分析思路

首先，暴力枚举从头到每一个右端点去验证肯定会超时，所以考虑优化。

我们从头遍历到尾，遍历过程中随时判断是不是发现了两个连续的 .、其他符号之类的不符合网站域名的内容。

然后可以看出在网站域名的基础上判断教育网站域名只需要记录截至当前出现的

T_i

的个数，再记录截至当前的

T_{m-1}

和

T_m

，并判断是否满足教育域名的要求就行了。

具体思路和细节看代码注释。

Part 3 参考代码

CPP

#include<bits/stdc++.h>
using namespace std;
int main() {
    //输入
    string s;
    cin >> s;
    //大写字母全部转成小写字母，方便后续判断
    for (int i=0;i<s.size();i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] = (char)(s[i]-'A'+'a');
        }
    }
    //截至当前出现了多少个Ti
    int c = 0;
    //Tm-1和Tm
    string l1 = "",l2 = "";
    //结尾补充一个点，这样最后一个Ti也能被验证
    s = s + '.';
    for (int i=0;i<s.size();i++) {
        if (s[i] == '.') {//一个Ti结束
            c++;//多找到了一个Ti
            //迭代更新截至当前的Tm-1和Tm
            l1 = l2;
            l2 = "";
        } else {
            l2 = l2 + s[i];//拼接到Tm后面
        }
        if ((c >= 3/*已经有了三个Ti*/ || (c == 2 && s[i] != '.')/*当前是第三个Ti也合法的*/) && l1 == "edu" && l2 == "cn"/*教育网站域名特殊判断*/) {
            cout << i+1 << " ";//找到一个答案并输出
        }
    }
    cout << endl;
    return 0;
}

有问题发在评论里，我很乐意回答哦。

题解：P13307 域名判断

文章操作