7-1 【模板】KMP字符串匹配 (20 分)

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

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

输入格式:

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

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

输出格式:

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

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>char s[1000005],t[1000005];
int next[1000005];
int lens,lent;void get_next()
{int i = 0, j = -1;next[i] = -1;while(i < lent){if(j == -1 || t[j] == t[i]){i++;j++;next[i] = j;}elsej = next[j];}
}void kmp()
{int i = 0,j = 0;while(i < lens){if(j == -1 || s[i] == t[j]){i++;j++;}else{j = next[j];}if(j == lent){printf("%d\n",i-j+1);}}
}int main()
{int i;gets(s);gets(t);lens = strlen(s);lent = strlen(t);get_next();kmp();for (i=1; i < lent; i++)printf("%d ",next[i]);printf("%d\n",next[lent]);return 0;
}

7-2 串的模式匹配 (25 分)

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

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

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

输入格式:

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

输出格式:

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

#include<stdio.h>
int main()
{char str1[1000001],str2[1000001];int i,n;gets(str1);scanf("%d",&n);getchar();for(i=0;i<n;i++){gets(str2);char *p=strstr(str1,str2);if(p!=NULL)//p地址不为空{for(;*p!='\0';p++)//结束条件是p内容结尾是0；接着p地址下移一个printf("%c",*p);printf("\n");}elseprintf("Not Found\n");}return 0;
}

7-3 字符串模式匹配 (5 分)

给定主串s和模式串p，编写程序输出p在s中出现的首位置，若p不在s中则输出-1。字符串下标从0开始。

输入格式:

输入为2行，第1行主串s，第2行为模式串p。主串和模式串长度不超过100000。

输出格式:

输出为2行，第1行为若干整数，表示模式串p的失败函数值，每个整数后一个空格；第2行为一个整数，表示p在s中出现的首位置，若p不在s中则输出-1。

#include<bits/stdc++.h>
using namespace std;
int nex[1000005];
char s[1000005],t[1000005];void getnext()
{int i=0,j=-1;nex[i]=-1;int lent=strlen(t);while(i<lent){if(j==-1||t[i]==t[j]){i++;j++;nex[i]=j;}elsej=nex[j];}for(int k=1;k<=lent;k++)cout<<nex[k]-1<<" ";cout<<endl;
}
void kmp()
{int i=0,j=0,pos;int flag=0;int lens=strlen(s);int lent=strlen(t);while(i<lens&&j<lent){if(j==-1||s[i]==t[j]){i++;j++;}elsej=nex[j];if(j==lent){pos=i-j;flag=1;}}if(flag==0)cout<<"-1";elseprintf("%d\n",i-j);
}int main()
{cin>>s>>t;getnext();kmp();
}

7-4 好中缀 (10 分)

我们称一个字符串S的子串T为好中缀，如果T是去除S中满足如下条件的两个子串p和q后剩余的字符串。

（1）p是S的前缀，q是S的后缀；

（2）p=q；

（3）p和q是满足条件(1)(2)的所有子串中的第二长者。

注意一个字符串不能称为自己的前缀或后缀。好中缀至少为空串，其长度大于等于0，不能为负数。

输入格式:

输入为一个字符串S，包含不超过100000个字母。

输出格式:

输出为一个整数，表示好中缀的长度。

#include<bits/stdc++.h>
using namespace std;
int nex[1000005];
char s[1000005],t[1000005];
int ans[1000005];void getnext()
{int i=0,j=-1;nex[i]=j;int lent=strlen(t);while(i<lent){if(j==-1||t[i]==t[j]){i++;j++;nex[i]=j;}else j=nex[j];}
}int main()
{scanf("%s",t);int lent=strlen(t);getnext();int i=nex[lent];//赋值t中最大的前缀值赋给iint j=0;while(i>0){ans[j++]=i;//ans数组从0开始挨个赋值最大的前缀，第二大的前缀...i=nex[i];//i值不断变化为次大的前缀}sort(ans,ans+lent,greater<int>());//把ans从0-lent个从大到小排序lent=lent-ans[1]*2;//求出第二大的前缀值if(lent<0)lent=0;printf("%d\n",lent);
}

7-5 三元组顺序表表示的稀疏矩阵转置Ⅱ (10 分)

三元组顺序表表示的稀疏矩阵转置Ⅱ。设a和b为三元组顺序表变量，分别表示矩阵M和T。要求按照a中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。

输入格式:

输入第1行为矩阵行数m、列数n及非零元素个数t。 按行优先顺序依次输入t行，每行3个数，分别表示非零元素的行标、列标和值。

输出格式:

按置入b中的顺序输出置入的位置下标，转置后的三元组行标、列标和值，数据之间用空格分隔，共t行。

#include<bits/stdc++.h>
using namespace std;
struct node
{int x;int y;int w;
}a[15],b[15];int main()
{int i,m,j,n,t;int ff=0;cin>>n>>m>>t;for(i=0;i<t;i++){cin>>a[i].x>>a[i].y>>a[i].w;}for(i=0;i<m;i++){for(j=0;j<t;j++){if(i==a[j].y){b[ff].x=i;b[ff].y=a[j].x;b[ff++].w=a[j].w;}}}for(i=0;i<t;i++){for(j=0;j<ff;j++){if(i==b[j].y){cout<<j<<" "<<b[j].x<<" "<<b[j].y<<" "<<b[j].w<<endl;}}}return 0;
}