PAT甲级1077 Kuchiguse 字符串匹配-蒲公英云

PAT甲级1077 Kuchiguse 字符串匹配

墨蓝 2023-06-14 11:55 74阅读 0赞

题意：

输入n句话，找出每句话中使用的相同的语气词，其实就是n个字符串中匹配最大相同子字符串问题

解题思路

1.读入每一句话，倒序后存入向量数组v
2.从第一个字符开始循环遍历比较每一个字符串相应位置，如果当前位置每一个字符串都相等，存入output字符串变量
3.逆序output字符串，输出，如果output是空表示不存在匹配的子字符串，输出nai

代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main()
{ 
    int n,cnt,min=300;
    string output="";
    vector<string> v;
    cin>>n;
    getchar();//读取换行 
    for(int i=0;i<n;i++)//读入每句话
    { 
        string a;
        getline(cin,a);
        int len=a.size();
        if(len<min)min=len;
        reverse(a.begin(),a.end());
        v.push_back(a);
    }
    for(cnt=0;cnt<=min;cnt++)//比较的字符下标 
    { 
        char cmp=v[0][cnt];
        for(int i=1;i<v.size();i++)//每一个字符串 
        { 
            if(v[i][cnt]!=cmp)
            { 
                cnt=min+1;
                break;
            }
        }
        if(cnt<=min)
        output+=cmp;
    }
    reverse(output.begin(),output.end());
    if(output!="")
    cout<<output<<endl;
    else cout<<"nai"<<endl;
    return 0;
}