关于算法-数据结构:PAT甲级1077-Kuchiguse

26次阅读

共计 783 个字符,预计需要花费 2 分钟才能阅读完成。

题目粗心:

给定 N 个字符串,求它们的公共后缀,如果没有就输入 nai

算法思路:

求字符串的公共后缀就得想到从后往前进行遍历雷同的字符了,为此应用 n 记录三个字符串的最小长度,作为遍历的最大长度,而后应用 i,j,k 别离作为 s1,s2,s3 的下标指针,只有 s1[i]==s2[j]&&s1[i]==s3[k] 就阐明以后字符为公共字符,增加到后果字符串 r 中,而后 –i,–j,–k, 否则就间接 break 退出循环。退出循环后,间接逆置字符串 r,如果 r 为空阐明没有公共后缀,输入 nai, 否则就输入 r 即可。

留神点:

这里的输出字符串得用 getline 承受一行,cin 遇到空格就进行输出了,同时在输出 N 后得用 getchar() 承受回车,防止被前面的 getline 承受到。

提交后果:

AC 代码:
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin>>N;
    getchar();// 承受回车
    string s1,s2,s3;
    getline(cin,s1);
    getline(cin,s2);
    getline(cin,s3);
    int n = min(min(s1.size(),s2.size()),s3.size());
    int i = s1.size()-1,j=s2.size()-1,k=s3.size()-1;//s1,s2,s3 的下标指针
    string r;
    for (int l = 0; l < n; ++l) {if(s1[i]==s2[j]&&s1[i]==s3[k]){r += s1[i];
            --i;
            --j;
            --k;
        } else{break;}
    }
    reverse(r.begin(),r.end());
    if(r.empty()){cout<<"nai";} else{cout<<r;}
    return 0;
}

正文完
 0