算法训练二（字符串、模式匹配、堆栈、队列）（含解题思路）（上）-创新互联

目录

创新互联公司是一家专注于成都网站建设、成都做网站与策划设计,隆化网站建设哪家好?创新互联公司做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:隆化等地区。隆化做网站价格咨询:028-86922220

7-1 好前缀

AC代码：

7-2 好后缀

AC代码：

7-3 【模板】KMP字符串匹配

AC代码：

7-5 接话茬

AC代码：

7-6 串的模式匹配

AC代码：

7-7 词频统计

AC代码：

7-9 匹配圆周率

AC代码：

7-10 堆栈操作合法性

AC代码：

7-11 括号匹配

AC代码：

7-12 表达式转换

AC代码：

7-13 求前缀表达式的值

AC代码：

---

因题集题目较多，下半部分题集请移步这里：

算法训练二（字符串、模式匹配、堆栈、队列）（含解题思路）（下）_清晨喝碗粥的博客-博客

7-1 好前缀

我们称一个字符串的前缀为好前缀，如果它满足如下条件：

（1）它在字符串中至少出现2次；

（2）满足条件（1）的最长者。

请编写程序计算一个字符串的好前缀长度，注意一个字符串不能称为自己的前缀。

输入格式：

输入为一个字符串，包含不超过10^5个字母。

输出格式：

输出为一个整数，表示输入字符串的好前缀长度。

输入样例1：

abcabce

输出样例1：

3

输入样例2：

ababaxxy

输出样例2：

3

思路：

写这道题之前建议读者优先了解字符串的KMP匹配算法，其中有一步是求next数组，本题就是KMP中的next数组应用

AC代码：

#includeusing namespace std;
void get_next(string s, vector&next) {
    int i, j;
    for (i = 1, j = 0; i< s.length(); i++) {
        while (j && s[i] != s[j])
            j = next[j - 1];
        if (s[i] == s[j])
            j++;
        next[i] = j;
    }
}
int main()
{
    int i, n, maxx = 0;
    string s;
    cin >>s;
    vectornext(s.length(), 0);
    get_next(s, next);
    for (i = 0; i< next.size(); i++) {
        maxx = max(maxx, next[i]);
    }
    cout<< maxx<< endl;

    system("pause");
    return 0;
}

7-2 好后缀

我们称一个字符串的后缀为好后缀，如果它满足如下条件：

（1）它在字符串中至少出现2次；

（2）满足条件（1）的最长者。

请编写程序计算一个字符串的好后缀长度，注意一个字符串不能称为自己的后缀。

输入格式：

输入为一个字符串，包含不超过10^5个字母。

输出格式：

输出为一个整数，表示输入字符串的好后缀长度。

输入样例1：

xacbacba

输出样例1：

4

输入样例2：

yxxabacaba

输出样例2：

3

输入样例3：

abc

输出样例3：

0

思路：

可以逆向思考7-1 好前缀，将字符串颠倒后即求好前缀即可

AC代码：

#includeusing namespace std;
void get_next(string s, vector&next) {
    int i, j;
    for (i = 1, j = 0; i< s.length(); i++) {
        while (j && s[i] != s[j])
            j = next[j - 1];
        if (s[i] ==s[j])
            j++;
        next[i] = j;
    }
}
int main()
{
    int i, j, k, n, maxx = 0;
    string s;
    cin >>s;
    vectornext(s.length(), 0);
    i = 0; j = s.length() - 1;
    while (i< j) {
        swap(s[i], s[j]);
        i++;
        j--;
    }
    get_next(s, next);
    for (i = 0; i< next.size(); i++) {
        maxx = max(maxx, next[i]);
    }
    cout<< maxx<< endl;
    
    system("pause");
    return 0;
}

7-3 【模板】KMP字符串匹配

给出两个字符串text和pattern，其中pattern为text的子串，求出pattern在text中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。

输入格式：

第一行为一个字符串，即为text。

第二行为一个字符串，即为pattern。

输出格式：

若干行，每行包含一个整数，表示pattern在text中出现的位置。

接下来1行，包括length(pattern)个整数，表示前缀数组next[i]的值，数据间以一个空格分隔，行尾无多余空格。

输入样例：

ABABABC
ABA

输出样例：

1
3
0 0 1

样例说明：

思路：

KMP算法模板，这里提供我的模板，因为是要所有子串在主串中出现的位置，所以我利用了一个res数组进行存储出现的下标，然后每次存储后更新一下j（指向next数组的指针）方便查询主串的后缀是否再次出现子串

AC代码：

#includeusing namespace std;
void get_next(string s, vector&next) {
    int i, j;
    for (i = 1, j = 0; i< s.length(); i++) {
        while (j && s[i] != s[j])
            j = next[j - 1];
        if (s[i] == s[j])
            j++;
        next[i] = j;
    }
}
vectorKMP_match(string s, string p, int begin, vector&next) {
    int i, j;
    vectorres;
    for (i = begin, j = 0; i< s.length(); i++) {
        while (j && s[i] != p[j])
            j = next[j - 1];
        if (s[i] == p[j])
            j++;
        if (j == p.length()) {
            res.push_back(i - p.length() + 1);
            j = next[j - 1];
        }
    }
    return res;
}
int main()
{
    int i, j, k, n;
    string s, p;
    cin >>s >>p;
    vectornext(p.length(), 0);
    vectorres;
    get_next(p, next);
    res = KMP_match(s, p, 0, next);
    for (i = 0; i< res.size(); i++) {
        cout<< res[i] + 1<< endl;
    }
    for (i = 0; i< next.size(); i++) {
        if (i == 0)
            cout<< next[i];
        else
            cout<< " "<< next[i];
    }
    
    system("pause");
    return 0;
}

7-5 接话茬

小CC最喜欢的就是接话茬，别人说一句，小CC就会接着他的话尾巴继续说下去，然后告诉他这是“顶针”修辞手法，活活将人气死。小XX也喜欢接话茬，每天都要与小CC比较技艺。然而无论是谁，都会被他们活活气死，因此两人总是难决胜负。后来小CC和小XX一起上了厦门大学，学习了校选课《接话茬数学原理与杠精的自我修养》，他们决定对两人的接话茬水平进行定量评估。

他们约定比赛规则如下，随机找一个倒霉的路人，路人说一句话，他们一起来接，他们接的话的前缀可以作为路人说的话后缀的长度就是那句话的水平。比如，别人说“abbbaabbc”，小CC接了一句“abbcefagd”，他所说的话的前缀“abbc”正是路人所说的话的后缀，长度为4，那么小CC的水平就是4；如果小XX说的是“xbbcadf”，无法构成路人所说的话的后缀，因此水平只有0。

现在，他们的比赛正式开始，由你来写一个程序充当裁判。

输入格式：

共三行，每行是一句话，长度均不超过10^6。

第一行是路人说的话。第二行是小CC说的话。第三行是小XX说的话。

输出格式：

仅一行，输出小CC和小XX接的话的水平，以空格分割，行末没有多余空格，以换行结束。

输入样例：

abbaabbc
abbc
xbb

输出样例：

4 0

思路：

这里我们如果从前往后遍历的话可能会运行超时，如果串足够长的话可能要遍历好久，所以我们可以从后往前进行遍历取子串操作，并且用两个变量记录双方的所接话茬的水平即可

AC代码：

#includeusing namespace std;
int main()
{  
    int i, j, k, n, res1 = 0, res2 = 0;
    string s, c, x;
    cin >>s >>c >>x;
    int minn = min(s.length(), c.length());
    for (i = minn; i >= 0; i--) {
        string temp1 = s.substr(s.length() - i, i);
        string temp2 = c.substr(0, i);
        if (temp1 == temp2) {
            res1 = temp1.size();
            break;
        }
    }
    minn = min(s.length(), x.length());
    for (i = minn; i >= 0; i--) {
        string temp1 = s.substr(s.length() - i, i);
        string temp2 = x.substr(0, i);
        if (temp1 == temp2) {
            res2 = temp1.size();
            break;
        }
    }
    cout<< res1<< " "<< res2<< endl;

    system("pause");
    return 0;
}

7-6 串的模式匹配

给定两个由英文字母组成的字符串 String 和 Pattern，要求找到 Pattern 在 String 中第一次出现的位置，并将此位置后的 String 的子串输出。如果找不到，则输出“Not Found”。

本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据0：小规模字符串，测试基本正确性；
• 数据1：随机数据，String 长度为 10^5，Pattern 长度为 10；
• 数据2：随机数据，String 长度为 10^5，Pattern 长度为 10^2；
• 数据3：随机数据，String 长度为 10^5，Pattern 长度为 10^3；
• 数据4：随机数据，String 长度为 10^5，Pattern 长度为 10^4；
• 数据5：String 长度为 10^6，Pattern 长度为 10^5；测试尾字符不匹配的情形；
• 数据6：String 长度为 10^6，Pattern 长度为 10^5；测试首字符不匹配的情形。

输入格式：

输入第一行给出 String，为由英文字母组成的、长度不超过 10^6 的字符串。第二行给出一个正整数 N（≤10），为待匹配的模式串的个数。随后 N 行，每行给出一个 Pattern，为由英文字母组成的、长度不超过 10^5 的字符串。每个字符串都非空，以回车结束。

输出格式：

对每个 Pattern，按照题面要求输出匹配结果。

输入样例：

abcabcabcabcacabxy
3
abcabcacab
cabcabcd
abcabcabcabcacabxyz

输出样例：

abcabcacabxy
Not Found
Not Found

思路：

KMP模板的简单变形，具体详见代码

AC代码：

#includeusing namespace std;
void get_next(string p, vector&next) {
    int i, j;
    for (i = 1, j = 0; i< p.length(); i++) {
        while (j && p[i] != p[j])
            j = next[j - 1];
        if (p[i] == p[j])
            j++;
        next[i] = j;
    }
}
string KMP_match(string s, string p, int begin) {
    if (s.length() == 1 || p.length() == 1)
        return "Not Found";
    vectornext(p.length(), 0);
    get_next(p, next);
    int i, j;
    for (i = begin, j = 0; i< s.length(); i++) {
        while (j && s[i] != p[j])
            j = next[j - 1];
        if (s[i] == p[j])
            j++;
        if (j == p.length()) {
            int cur = i - p.length() + 1;
            return s.substr(cur, s.length() - cur + 1);
        }
    }
    return "Not Found";
}
int main()
{
    int i, j, k, n;
    string s;
    cin >>s >>n;
    vectornums(n, ""), res;
    for (i = 0; i< n; i++) {
        cin >>nums[i];
    }
    for (i = 0; i< n; i++) {
        res.push_back(KMP_match(s, nums[i], 0));
    }
    for (i = 0; i< n; i++) {
        cout<< res[i]<< endl;
    }

    system("pause");
    return 0;
}

7-7 词频统计

请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频大的前10%的单词。

所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。

输入格式：

输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。

输出格式：

在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。

随后按照词频递减的顺序，按照词频:单词的格式输出词频大的前10%的单词。若有并列，则按递增字典序输出。

输入样例：

This is a test.

The word "this" is the word with the highest frequency.

Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee.  But this_8 is different than this, and this, and this...#
this line should be ignored.

输出样例：（注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出。）

23
5:this
4:is

思路：

我是先将所有的大写英文字母在输入时就转化为了小写的英文字母，这样方便后面的判断，利用map进行记录每个单词出现的次数，最后利用一个数组进行存储对其自定义排序，最终输出即可

AC代码：

#includeusing namespace std;
bool cmp(paira, pairb) {
    if (a.first == b.first)
        return a.second< b.second;
    return a.first >b.first;
}
int main()
{
    int i, j, k, n;
    string s = "";
    mapmp;
    vector>res;
    char op;
    i = 0;
    while (scanf("%c", &op) && op != '#') {
        if (op >= 'A' && op<= 'Z')
            op = op + 32;
        s += op;
    }
    i = 0;
    while (i< s.length()) {
        if (s[i] >= 'a' && s[i]<= 'z'|| s[i] >= '0' && s[i]<= '9' || s[i] == '_') {
            string temp = "";
            j = i;
            while (j< s.length() && (s[j] >= 'a' && s[j]<= 'z' || s[j] >= '0' && s[j]<= '9' || s[j] == '_'))
                j++;
            temp = s.substr(i, min(j - i, 15));
            mp[temp]++;
            i = j;
        } else 
            i++;
    }
    cout<< mp.size()<< endl;
    for (auto & m : mp) {
        res.push_back(pair(m.second, m.first));
    }
    sort(res.begin(), res.end(), cmp);
    for (i = 0; i< res.size() / 10; i++) {
        cout<< res[i].first<< ":"<< res[i].second<< endl;
    }

    system("pause");
    return 0;
}

7-9 匹配圆周率

使用KMP算法实现串匹配你在课堂上想必已经烂熟于心了，不过咱们先来聊一聊圆周率π。有的人猜想，无理数π的小数部分包含了宇宙中的大秘密，比如你的生日、你男朋友/女朋友的生日，甚至是你的银行卡的账号密码。将它穷尽是一件不可能的事情，但是我们可以对前面的部分进行考察。
在这个题目中，不允许使用编程语言内置的字符串匹配算法，例如C语言中的strcmp。

如果你想查找自己的π信息，可以登录网站The Pi-Search Page

输入格式：

输入为两行，第一行为圆周率小数部分的节选s，长度不超过10^6；第二行是要查找的数字串t，长度不超过10^6。可以假设，输入都是0~9这样的数字。

输出格式：

输出t在s中首次出现的位置。如果t未在s中出现，则输出-1，以换行结尾。

输入样例1：

821999052039574422
19990520

输出样例1：

2

输入样例2：

881994082555083527588321827035
19940825

输出样例2：

2

输入样例3：

141592653
264

输出样例3：

-1

思路：

简单KMP算法，将数字以字符串的形式输入即可

AC代码：

#includeusing namespace std;
void get_next(string p, vector&next) {
    int i, j;
    for (i = 1, j = 0; i< p.length(); i++) {
        while (j && p[j] != p[i])
            j = next[j - 1];
        if (p[j] == p[i])
            j++;
        next[i] = j;
    }
}
int KMP_match(string s, string p, int begin, vector&next) {
    int i, j;
    for (i = 1, j = 0; i< s.length(); i++) {
        while (j && s[i] != p[j])
            j = next[j - 1];
        if (s[i] == p[j])
            j++;
        if (j == p.length()) {
            return i - p.length() + 1;
        }
    }
    return -1;
}
int main()
{
    int i, j, n, res;
    string s, p;
    cin >>s >>p;
    if (s == p) {
        cout<< 0<< endl;
        return 0;
    }
    vectornext(p.length(), 0);
    get_next(p, next);
    res = KMP_match(s, p, 0, next);
    cout<< res<< endl;

    system("pause");
    return 0;
}

7-10 堆栈操作合法性

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

输入格式：

输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。

输出格式：

对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。

输入样例：

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例：

YES
NO
NO
NO

思路：

栈的简单模拟，这里无非是有几个注意点

1：入栈时不能超出栈的容量

2：出栈时栈不能为空且栈顶不能为‘X’

3：遍历完序列后栈应为空栈

AC代码：

#includeusing namespace std;
string solve(int m) {
    int i, j, k, n;
    string s;
    cin >>s;
    stackst;
    for (i = 0; i< s.length(); i++) {
        if (s[i] == 'S') {
            if (st.size() >= m)
                return "NO";
            st.push(s[i]);
        } else {
            if (st.empty() || st.top() != 'S')
                return "NO";
            st.pop();
        }
    }
    if (!st.empty())
        return "NO";
    return "YES";
}
int main()
{
    int t, m;
    cin >>t >>m;
    vectorres;
    while (t--) {
        res.push_back(solve(m));
    }
    for (int i = 0; i< res.size(); i++) {
        cout<< res[i]<< endl;
    }

    system("pause");
    return 0;
}

7-11 括号匹配

给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。

输入格式：

输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。

输出格式：

如果括号配对，输出yes，否则输出no。

输入样例1：

sin(10+20)

输出样例1：

yes

输入样例2：

{[}]

输出样例2：

no

思路：

栈的简单模拟，详见代码

AC代码：

#includeusing namespace std;

int main()
{
    stacka;
    int flag = 1;
    char * c = new char[200];
    cin.getline(c, 200, '\n');
    int i = 0;
    while(i< strlen(c) && flag)
    {
    	if(c[i]=='('||c[i]=='['||c[i]=='{')   		//左括号，入栈 
    		a.push(c[i]);
    		
    	if(c[i]==')'||c[i]==']'||c[i]=='}')		//右括号，匹配左括号 
    	{
    		if(a.size()==0)
    			flag = 0;
    		else
    		{
    			char x = a.top();
    			if(c[i]==')'&&x!='(')
    				flag = 0;
    			if(c[i]==']'&&x!='[')
    				flag = 0;
    			if(c[i]=='}'&&x!='{')
    				flag = 0;
			}
    		if(flag)
    			a.pop();
    	}
        i++;
	}
    
    if(flag)
    	cout<< "yes"<< endl;
    else
    	cout<< "no"<< endl;
    system("pause");
    
    return 0;
}

7-12 表达式转换

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式：

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、/以及左右括号()，表达式不超过20个字符。

输出格式：

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例：

2+3*(7-4)+8/4

输出样例：

2 3 7 4 - * + 8 4 / +

思路：

这里我们要事先了解如何将中缀表达式转换为后缀表达式，首先初始化一个栈，用于保存暂时还不能确定运算顺序的运算符，从左到右处理各个元素，直到末尾，可能会遇到三种情况

1：遇到操作数，直接加入后缀表达式

2：遇到界限符，遇到”(”直接入栈，遇到”)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止，注意：“(”不加入后缀表达式

3：遇到运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到”(”或栈空时则停止，之后再把当前运算符入栈

按照上述方法处理完所有字符后，将栈中剩余的运算符依次弹出，并加入后缀表达式

这里需要注意一点的是测试点会有负号以及(+3)这种情况的存在，在最后进行依次判断即可

AC代码：

#includeusing namespace std;
maptemp;
//可以用一个map来记录运算符的优先级从而方便后续判断
void Init_map() {
    temp['+'] = 1;
    temp['-'] = 1;
    temp['*'] = 2;
    temp['/'] = 2;
}
int main()
{
    int i, j, k, n;
    string s, item, res = "";
    cin >>s;
    Init_map();
    stackst;
    for (i = 0; i< s.length(); i++) {
        if (s[i] >= '0' && s[i]<= '9' || s[i] == '.') {
            res += s[i];
            item += s[i];
        }
        else {
            if (item != "") {
                res += ' ';
                item.clear();
            }
            if (s[i] == ')') {
                while (!st.empty() && st.top() != '(') {
                    res += st.top();
                    res += ' ';
                    st.pop();
                }
                st.pop();
                continue;
            } else if(s[i] != '(') {
                while (!st.empty() && st.top() != '(' && temp[st.top()] >= temp[s[i]]) {
                    res += st.top();
                    res += ' ';
                    st.pop();
                }
            }
            if (i == 0 && s[i] == '+')
                continue;
            else if (i == 0 && s[i] == '-') {
                res+= '-';
                item += '-';
                continue;
            }
            if (i >0 && s[i] == '+' && (s[i - 1] == '(' || s[i - 1] == '+'))
                continue;
            else if (i >0 && s[i] == '-' && (s[i - 1] == '(' || s[i - 1] == '+')) {
                res += '-';
                item += '-';
                continue;
            } else if (i >0 && s[i] == '-' && (s[i - 1] == '(' || s[i - 1] == '-')) {
                st.pop();
                st.push('+');
                continue;
            }
            st.push(s[i]);
        }
    }
    if (item != "")
        res += ' ';

    while (!st.empty()) {
        res += st.top();
        res += ' ';
        st.pop();
    }
    int len = res.length() - 1;
    while (res[len] == ' ')
        len--;
    for (i = 0; i<= len; i++) {
        cout<< res[i];
    }

    system("pause");
    return 0;
}

7-13 求前缀表达式的值

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

输入格式：

输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、/以及运算数，不同对象（运算数、运算符号）之间以空格分隔。

输出格式：

输出前缀表达式的运算结果，保留小数点后1位，或错误信息ERROR。

输入样例：

+ + 2 * 3 - 7 4 / 8 4

输出样例：

13.0

思路：

我们可以利用栈，如果遇到运算符，则运算符直接入栈，如果遇到操作数，则两次弹出栈顶的内容进行第一次弹出栈顶的运算符的操作，最终将结果入栈即可，遍历完成后栈内的最后一个数即是运算的最终结果

AC代码：

#includeusing namespace std;
int main()
{
    int i, j, k, n;
    string op;
    vectornums;
    stackst;
    while (cin >>op) {
        nums.push_back(op);
    }
    for (i = nums.size() - 1; i >= 0; i--) {
        if (nums[i] != "+" && nums[i] != "-" && nums[i] != "*" && nums[i] != "/")
            st.push(stod(nums[i]));
        else {
            double a, b;
            if (st.size()< 2) {
                cout<< "ERROR"<< endl;
                return 0;
            }
            a = st.top();
            st.pop();
            b = st.top();
            st.pop();
            if (nums[i] == "+")
                st.push(a + b);
            else if (nums[i] == "-")
                st.push(a - b);
            else if (nums[i] == "*")
                st.push(a * b);
            else {
                if(b == 0) {
                    cout<< "ERROR"<

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前标题：算法训练二（字符串、模式匹配、堆栈、队列）（含解题思路）（上）-创新互联
网站路径：http://bjjierui.cn/article/dhpiep.html