[编程题]字符串匹配
- 热度指数：12242 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
读入数据string[ ]，然后读入一个短字符串。要求查找string[ ]中和短字符串的所有匹配，输出行号、匹配字符串。匹配时不区分大小写，并且可以有多个用中括号表示的模式匹配。如“aa[123]bb”，就是说aa1bb、aa2bb、aa3bb都算匹配。
输入描述:
输入有多组数据。 每组数据第一行输入n(1<=n<=1000)，从第二行开始输入n个字符串（不含空格），接下来输入一个匹配字符串。
输出描述:
输出匹配到的字符串的行号和该字符串（匹配时不区分大小写）。
示例1
输入
4 Aab a2B ab ABB a[a2b]b
输出
1 Aab 2 a2B 4 ABB
正则表达式有时候挺好用的，特别是该题可能出现多个‘[’,']'。
#include<iostream>
(720)#include<algorithm>
#include<string>
(765)#include<map>
#include<vector>
(721)#include<iomanip>
#include<regex>
using namespace std;
int main()
{
string s;
int n;
while (cin>>n)
{
vector<string> con;
for (int i = 0; i < n; i++)
{
cin >> s;
con.push_back(s);
}
string pa;
cin >> pa; //正则匹配表达式，文法
//int a = pa.find('[');
//int b = pa.find(']');
//string i = pa.substr(0, a);
//string j = pa.substr(a, b - a + 1);
//string k = pa.substr(b + 1, pa.size() - b - 1);
regex pattern(pa,regex::icase); //不区分大小写匹配
smatch result;
for (int i = 0; i < con.size(); i++)
{
if(regex_match(con[i], result, pattern))
cout << i + 1 << " "<<con[i] << endl;
}
}
}
发表于 2020-03-19 23:52:48
回复(2)
暴力匹配判断
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 10005
char s[maxn][maxn], t[maxn];
int n;
int equal(char c1, char c2){
if(c1 >= 'a' && c1 <= 'z'){
if(c2 >= 'A' && c2 <= 'Z') c2 = 'a' + (c2 - 'A');
return c1 == c2 ? 1 : 0;
}
else if(c1 >= 'A' && c1 <= 'Z'){
if(c2 >= 'a' && c2 <= 'z') c2 = 'A' + (c2 - 'a');
return c1 == c2 ? 1 : 0;
}
else{
return c1 == c2 ? 1 : 0;
}
}
int ck(char _s[], char _c, int l, int r){
int i;
for(i = l + 1; i < r; i++){
if(equal(_c, _s[i]) == 1){
return 1;
}
}
return 0;
}
int judge(char _s[], char _t[]){
int i = 0, j = 0;
int ls = strlen(_s), lt = strlen(_t);
while(i < ls && j < lt){
if(_t[j] == '['){
int l = j;
int r = l;
for(;;r++){
if(_t[r] == ']') break;
}
if(ck(_t, _s[i], l, r) == 1){
i++; j = r + 1;
}
else{
return 0;
}
}
else{
if(equal(_s[i], _t[j]) == 1){
i++; j++;
}
else{
return 0;
}
}
}
if(i == ls && j == lt) return 1;
else return 0;
}
int main()
{
int i;
while(~scanf("%d", &n)){
for(i = 0; i < n; i++){
scanf("%s", s[i]);
}
scanf("%s", t);
for(i = 0; i < n; i++){
if(judge(s[i], t) == 1){
printf("%d %s\n", i + 1, s[i]);
}
}
}
return 0;
}
发表于 2019-07-08 11:01:34
回复(2)
python 代码， 使用 re.search 方法匹配
import sys import re line = sys.stdin.readline() while line: ss = [] for _ in range(int(line)): ss.append(raw_input()) patt = raw_input() for i,s in enumerate(ss): m = re.search(patt, s, re.I) if m is not None: print i + 1, s line = sys.stdin.readline()
发表于 2016-12-16 16:44:54
回复(0)
#include"iostream"
#include"vector"
using namespace std;
int main(){
int n;
while(cin>> n){
getchar();
vector<string> v(n+ 1);
for(int k= 1; k<= n; k++){ getline(cin, v[k]);}// 输入数据串
string mode;cin>> mode;// 输入模式串
int len2= mode.length();
for(int k= 0; k< len2; k++){ mode[k]= tolower(mode[k]);}// 不区分大小写 模式串全部转小写
for(int k= 1; k<= n; k++){
int len, i, j2;
i= j2= 0, len= v[k].length();// 双指针
while(i< len&& j2< len2){
if(mode[j2]== '['){// 模式串遇到[
int loc= mode.find(']', j2+ 1);// 确定]的位置
int xb= mode.find(tolower(v[k][i]), j2+ 1);// 在[、]之间寻找数据串的字符
if(xb< loc&& xb> j2){i++; j2= loc+ 1;}// 如果在模式串[、]之间有数据串的字符 数据串指针后移一位 模式串指针移动到]后
else{break;}//
}else if(tolower(v[k][i])== mode[j2]){// 模式串非[ 则与主串字符比较 若相同 双指针后移
i++;j2++;
}else{break;}// 否则匹配失败
}
if(j2== len2){cout<< k<< " "<< v[k]<< endl;}
}
}
}
发表于 2022-02-08 20:17:27
回复(0)
#include<iostream>
#include<regex>//正则表达式头文件
using namespace std;
//建议正则表达式来做，参考资料
//https://www.cnblogs.com/sgdd123/p/7778599.html
int main(void)
{
int n;
string s[1000];
while(cin >> n)
{
for(int i = 0;i < n;i++)
{
string temp;
cin >> temp;
s[i] = temp;
}
string s_match;
cin >> s_match;
regex r(s_match,regex::icase);//正则表达式的声明，regex::icase 不区分大小写
for(int i = 0;i < n;i++)
{
string temp = s[i];
if(regex_match(temp,r))//regex_match完全匹配；不完全匹配用regex_search
cout << i + 1 << ' ' << temp << endl;
}
}
return 0;
}
发表于 2021-02-10 15:48:29
回复(0)
#include<iostream>
#include<string>
using namespace std;
void ToLower(string &pattern)
{
for(int j = 0;j < pattern.size();j++)
{
if(pattern[j] >= 'A' && pattern[j] <= 'Z')
{
pattern[j] = char(pattern[j] + 32);
}
}
}
int main()
{
int n;
string pattern;
while(cin >> n)
{
string s[n],p[n];
for(int i = 0;i < n;i++)
{
cin >> s[i];
p[i] = s[i];
ToLower(s[i]);
}
cin >> pattern;
ToLower(pattern);
for(int i = 0;i < n;i++)
{
int j = 0,k = 0;
while(j < s[i].size() && k < pattern.size())
{
bool flag = false;
if(pattern[k] == '[')
{
k++;
while(pattern[k] != ']')
{
if(pattern[k] == s[i][j])
{
flag = true;
}
k++;
}
if(!flag){
break;
}
else
{
k++;
j++;
}
}
else if(s[i][j] == pattern[k])
{
j++;
k++;
}
else
{
break;
}
}
if(j == s[i].size() && k == pattern.size())
{
cout << i + 1 << " " << p[i] << endl;
}
}
}
}
发表于 2021-01-20 19:37:15
回复(0)
#include<iostream>
#include<queue>
using namespace std;
int main(){
int n;
while(cin>>n){
string str[n],str1[n],_str;
bool show[n];
for(int i = 0; i<n; i++){
show[i] =false;
cin>>str[i]; //用于输出
str1[i] = str[i]; //所有大小写统一，用于比较
int l = str[i].size();
for(int j = 0; j<l; j++)
if(str1[i][j]>='A' && str1[i][j] <= 'Z')
str1[i][j] = str1[i][j] + 'a' - 'A';
}
cin>>_str;
int len = _str.size();
for(int j = 0; j<len; j++)
if(_str[j]>='A' && _str[j]<= 'Z')
_str[j] = _str[j] + 'a' - 'A'; //统一大小写
int pos1 = 0,pos2;
queue<string> kmp; //创建队列用于存放要匹配字符串
kmp.push(_str);
while(!kmp.empty()){ //去除所有【】，并将所有可能入队
string a = kmp.front();
if(a.find('[') == string::npos)
break;
else{
kmp.pop();
pos1 = a.find('[');
pos2 = a.find(']');
for(int i = pos1+1; i<pos2; i++){
string _str1 = a.substr(0,pos1) + a[i] + a.substr(pos2+1);
kmp.push(_str1);
}
}
}
while(!kmp.empty()){ //比较
string a = kmp.front();
kmp.pop();
for(int j = 0; j<n; j++){
if(show[j] == false){
if(str1[j].find(a) != string::npos)
show[j] = true;
}
}
}
for(int j = 0; j<n; j++)
if(show[j] == true) //输出
cout<<j+1<<" "<<str[j]<<endl;
}
}
编辑于 2020-04-21 16:32:30
回复(0)
Java
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()){
int n = scanner.nextInt();
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < n; i++) list.add(scanner.next());
String r = scanner.next().toLowerCase();
for (int i = 0; i < list.size(); i++) {
if (Pattern.matches(r,list.get(i).toLowerCase()))
System.out.println(i+1+" "+list.get(i));
}
}
}
}
编辑于 2020-03-20 10:52:20
回复(0)
对于688测试不通过需要注意的两点：
1.匹配的【】可能有多个
2.匹配时不区分大小写！！的情况要考虑全，这里很多大小写的a和c，很容易漏一些情况，然后就不能通过
对于这个多个括号匹配，我是直接把所有的【】和里面的字符串用一个*取代，然后把里面的字符串按中括号出现的顺序依次丢到一个字符串数组中，匹配的时候，一旦遇到了*就要考虑是否能在相应的数组中找到str[i][j]的大小写或者str[i][j]是否为*。
#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
string str[n],cmp[100],org;
for(int i=0;i<n;cin>>str[i++]);
cin>>org;
int be,en,olen;
int num=0;
while((be=org.find('['))!=-1)
{
en=org.find(']');
cmp[num++]=org.substr(be,en);
org.replace(be,en-be+1,"*");
}
olen=org.length();
for(int i=0;i<n;i++)
{
num=0;
if(str[i].length()!=olen) continue;
for(int j=0;j<olen;j++)
{
char c = str[i][j];
char d = tolower(c);
char e = toupper(c);
if(org[j]=='*'){
if(cmp[num].find(d)==-1&&cmp[num].find(e)==-1&&c!='*') break;
num++;
}
else if(tolower(org[j])!= d) break;
if(j+1==olen) cout<<i+1<<' '<<str[i]<<endl;
}
}
}
return 0;
}
发表于 2019-06-08 16:31:12
回复(0)
#include<iostream>
#include<string.h>
using namespace std;
string str[1000];
int main(){
int n;
string s;//待比较模式串
while(cin>>n){
for(int i=0;i<n;i++) cin>>str[i];
cin>>s;
int length=s.size();
int real=0;//待比较模式串真正意义的长度
bool mark=false;
for(int i=0;i<length;i++){//求出real
if(s[i]!='['&&mark==false){
real++;
}
else{
mark=true;
if(s[i]!=']')
continue;
else{
mark=false;
real++;
}
}
}
int differ='A'-'a';
for(int i=0;i<n;i++){
bool flag=false;
if(str[i].size()!=real) continue;
else{
for(int j=0,t=0;j<real;j++,t++){
if(str[i][j]==s[t]||str[i][j]-s[t]==differ||s[t]-str[i][j]==differ){
flag=true;
continue;//字符匹配 进入下一位置循环
}
else{
if(s[t]=='['){//字符不匹配 且该位置是'['，在[]中搜索 检验是否匹配
for(;s[t]!=']';t++){
if(str[i][j]==s[t]||str[i][j]-s[t]==differ||s[t]-str[i][j]==differ){
flag=true;
}
}
}
else{//字符不匹配 且该位置不是'['，直接跳出循环 匹配失败
flag=false;
break;
}
}
}
}
if(flag) cout<<i+1<<" "<<str[i]<<endl;
}
}
return 0;
}
发表于 2019-02-12 22:39:52
回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt())
{
int n = sc.nextInt();
List<String> list = new ArrayList<>();
while(n-- != 0)
list.add(sc.next());
String pattern = sc.next().toLowerCase();
for(int i = 1; i <= list.size(); i++)
{
String current = list.get(i - 1);
if(current.toLowerCase().matches(pattern))
System.out.println(i + " " + current);
}
}
sc.close();
}
}
发表于 2018-08-02 10:36:53
回复(0)
C语言AC#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int main(){
int n,i,j,k,len;
char a[1001][100];
char b[100];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",&a[i]);
}
scanf("%s",&b);
for(k=0;k<n;k++){
i=0;j=0;
len=strlen(b);
while((a[k][i]==b[j] || abs(a[k][i]-b[j])==32 || b[j]=='[')&& j<len){
if(b[j]=='['){
j++;
while((b[j]!=a[k][i] && abs(a[k][i]-b[j])!=32) && b[j]!=']'){
j++;
}
if(b[j]==']')
break;
if(b[j]==a[k][i] || abs(a[k][i]-b[j])==32){
while(b[j]!=']')
j++;
j++;
i++;
}
}else{
i++;
j++;
}
if(j==len){
if(k<n-1)
printf("%d %s\n",k+1,a[k]);
else
printf("%d %s",k+1,a[k]);
}
}
}
return 0;
}
编辑于 2018-06-13 14:37:05
回复(0)
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int main()
{
int n=1;
while(cin>>n){
string str[n];
for(int i=0;i<n;i++){
cin>>str[i];
}
string parten;
cin>>parten;
int count=0;
int lcount = 0;
// 得到模式串的长度
for(int i =0;i<parten.size();i++){
if(parten[i]!='[')
lcount++;
else{
while(parten[i]!=']')
i++;
lcount++;
}
}
for(int i=0;i<n;i++){
count = 0;
int k=0;
// cout<<endl<<str[i]<<endl;
for(int j=0;j<str[i].size();j++){
if(parten[k] != '['){
// lcount++;
string left="";
left+=(str[i][j]);
string right="";
right += parten[k];
// cout<<endl<<"str[i][j] "<<str[i][j]<<" partten[k] "<<parten[k]<<" stricmp "<<stricmp(left.c_str(),right.c_str())<<endl;
if(strcasecmp(left.c_str(),right.c_str()) != 0)
break;
else
count++;
}else{
k++;
// lcount++;
while(parten[k]!=']'){
string left="";
left+=(str[i][j]);
string right="";
right += parten[k];
if(strcasecmp(left.c_str(),right.c_str()) == 0)
{
count++;
while(parten[k]!=']')
k++;
}else
{
k++;
}
}
}
k++;
//cout<<endl<<"after] : "<<parten[k];
// cout<<k<<endl;
}
// cout<<endl<<"lcount"<<lcount<<endl;
if(count == str[i].size()&&count == lcount)
cout<<i+1<<" "<<str[i]<<endl;
else
continue;
}
//cout<<endl<<"END";
}
}
发表于 2018-06-02 12:01:33
回复(0)
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
char pat[1000];
char str[1000][1000];
int n;
while(scanf("%d",&n)!=EOF)//EOF或-1终止
{
getchar();
for(int i=0; i<n; i++)
{
gets(str[i]);
}
gets(pat);
int l='A'-'a';
bool tag=false;
int v=0;
for(int i=0; i<strlen(pat); i++)
{
if(pat[i]>='A'&&pat[i]<='Z')
pat[i]-=l;
if(pat[i]=='[')
tag=true;
if(pat[i]==']')
tag=false;
if(tag==true)
v++;
}
int plen=strlen(pat)-v;
for(int i=0; i<n; i++)
{
int len=strlen(str[i]);
if(len!=plen)
continue;
bool flag=true;
int offset=0;
int t=0;
for(int j=0; j<len; j++,t++)
{
if(str[i][j]!=pat[t]&&str[i][j]!=pat[t]+l)
{
flag=false;
if(pat[t]=='[')
{
bool fl=false;
for(; pat[t]!=']'; t++)
{
if(str[i][j]==pat[t]||str[i][j]==pat[t]+l)
fl=true;
}
if(fl)
flag=true;
}
else
{
flag=false;
break;
}
}
}
if(flag)
printf("%d %s\n",i+1,str[i]);
}
}
return 0;
}
发表于 2017-04-08 13:26:15
回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n;
vector<string> vs;
while (cin >> n) {
vs.clear();
for (int i=0; i<n; i++) {
string s;
cin >> s;
vs.push_back(s);
}
string s;
cin >> s;
for (int i=0; i<n; i++) {
int j1 = 0;
int j2 = 0;
string s2(vs[i]);
while (true) {
if (j1 < s.size() && j2 == s2.size()
|| j1 == s.size() && j2 < s2.size()) {
break;
}
if (j1 == s.size() && j2 == s2.size()) {
cout << (i + 1) << ' ' << s2 << endl;
break;
}
if (s[j1] == '[') {
bool flag = false;
while (s[++j1] != ']') {
if ((s[j1] | 32) == (s2[j2] | 32)) {
flag = true;
}
}
if (!flag) {
break;
}
j1++;
j2++;
}
else {
if ((s[j1] | 32) == (s2[j2] | 32)) {
j1++;
j2++;
}
else {
break;
}
}
}
}
}
}
发表于 2016-03-23 12:57:35
回复(1)
代码总共写过三遍，最后还是不对，折腾了一上午才通过，差点哭出来
#include <stdio.h>
#include <string.h>
#define N 1001
#define LEN 1001
int IsLetter(char c)//判断一个字符是不是字母、大写还是小写
{
if('a'<=c&&c<='z') return 1;
else if('A'<=c&&c<='Z') return 1;
else return 0;
//返回2表示大写，返回1表示小写，返回0表示不是字母
}
int IsSame(char a, char b)//判断两个字符是否一致，不区分大小写
{
if(IsLetter(a)==0||IsLetter(b)==0)//若ab有一个不是字母，那就严格匹配
{
if(a==b) return 1;
else return 0;
}
else//若ab都是字母
{
if(a==b) return 1;
else if(a==b+'A'-'a') return 1;
else if(a==b+'a'-'A') return 1;
else return 0;
}
}
int Bracket(char s[], char b[], int &pos_s, int &pos_b)//对比括号内的内容
{
int i=pos_b+1;//指向'['之后的位置，准备开工
while(b[pos_b]!=']') pos_b++;//找到']'
pos_b++;//b的指针指向']'之后
while(i<pos_b-1)
{
if(IsSame(b[i], s[pos_s]))
{
pos_s++;
return 1;
}
i++;
}
return 0;
}
int MatchWith(char s[], char b[])//判断两个串是否匹配
{
int ls=strlen(s), lb=strlen(b);
int pos_s=0, pos_b=0;
while(pos_s<ls&&pos_b<lb)
{
if(IsSame(b[pos_b], s[pos_s]))
{
pos_s++;
pos_b++;
}
else if(b[pos_b]=='[')//准备处理括号
{
if(!Bracket(s, b, pos_s, pos_b)) break;
//若括号内匹配失败，则跳出循环(也会顺便返回0)
}
else return 0;
}
if(s[pos_s]=='\0'&&b[pos_b]=='\0') return 1;//两串同时结束才算匹配
else return 0;
}
int main()
{
int i, n;
char s[N][LEN];//大约占1MB空间，问题不大
char b[LEN];
while(scanf("%d", &n)!=EOF)
{
for(i=0; i<n; i++) scanf("%s", s[i]);
scanf("%s", b);
for(i=0; i<n; i++)
{
if(MatchWith(s[i], b)) printf("%d %s\n", i+1, s[i]);
}
}
return 0;//大功告成
}
编辑于 2018-02-08 11:34:57
回复(11)
人生苦短，我用正则
#include <cstdio>
#include <iostream>
#include <string>
#include <regex>
using namespace std;
string st[1001];
int main () {
int n;
scanf("%d ", &n);
for (int i=1; i<=n; ++i)
getline(cin, st[i]);
getline(cin, st[0]);
regex r(st[0], regex::icase); // regex::icase 不区分大小写
for (int i=1; i<=n; ++i)
if (regex_match(st[i], r)) // 这是完全匹配，部分匹配用regex_search
cout << i << ' ' << st[i] << endl;
} 
编辑于 2020-02-16 17:14:36
回复(7)
做了一个晚上总算是用不到50行代码比较简洁的解决了，题目有点坑，重点如下：
1、题目要求字符串匹配意思准确来讲应该是完全相等（在忽视大小写情况下），而且数据量比较小，不需要考虑蛮力匹配还是KMP的问题，这是一个大坑
2、字符串大小写处理可用cctype库里的 isalpha()、tolower()等函数，自己写一个equal()判等函数简洁地写出
3、题目表意错误，实际上最后一行存在多括号。最开始想的是用string的find、erase函数，把每一个括号内的字符放在一个string里并用vector储存，后面每次遇括号时依次匹配，也能AC。后来想清楚了，其实其实都是多余的，直接双指针逐一比对就好了时间复杂度O(m*n)，数据量小，时间绰绰有余。代码如下：
#include<iostream>
#include<string>
using namespace std;
bool equal(char a, char b) //判等函数
{
if(isalpha(a)&&isalpha(b)) //若a、b同为字母，判断两者的小写是否相等
return tolower(a) == tolower(b); //实测，tolower在已是小写时不操作
else return a == b; //否则判其是否严格相等
}
int main()
{
int n;
while (scanf("%d\n", &n) != EOF) { //多组输入
string text[1005], pattern;
for (int i = 0; i < n; cin >> text[i++]);
cin >> pattern; //输入文本串、模式串
for (int i = 0; i < n; i++) {
bool match = true;
int j = 0, k = 0; //双指针指向两者位置
for (; j < pattern.size()&&k < text[i].size();j++,k++) {
if (pattern[j] == '[') { //遇到'['则单独扫描j
bool hit = false;
while (++j<pattern.size() && pattern[j] != ']') {
if (equal(text[i][k], pattern[j]))
hit = true; // j退出循环时已经与k同步
}
if (!hit) { //扫描'[]'内字符后仍无法匹配则跳出
match = false;
break;
}
}
else if (!equal(text[i][k], pattern[j])) { //匹配失败跳出
match = false;
break;
}
}
if (j != pattern.size() || k != text[i].size()) match = false;
//匹配成功则必然j、k都到上限，这一步是防止包含情况出现，如ab,A[a2b]b
if(match) cout << i + 1 << " " << text[i] << endl;
}
}
return 0;
}
编辑于 2020-02-29 23:26:06
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
