7-1 串的模式匹配 (30分)
给定一个主串S（长度<=106）和一个模式T（长度<=105），要求在主串S中找出与模式T相匹配的子串，返回相匹配的子串中的第一个字符在主串S中出现的位置。
输入格式:
输入有两行： 第一行是主串S； 第二行是模式T.
输出格式:
输出相匹配的子串中的第一个字符在主串S中出现的位置。若匹配失败，输出0.
输入样例:
在这里给出一组输入。例如：
输出样例:
在这里给出相应的输出。例如：
首先有kmp算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include <iostream>
#include <string>
#include <cstring>
using namespace std;
typedef int Status;
typedef struct
{
char *ch;
int length;
}HString;
//把string类型变成char*类型
char* trans(string s)
{
int size = s.length();
char* s1=new char[size];
strcpy(s1,s.c_str());
return s1;
}
//生成串s1
Status Strassign(HString &s1,char *char1)
{
int i;
char *c;
//if(s1.ch)free(s1.ch);
//i为char1长度
for (i = 0,c=char1; *c ; ++c,++i) ;
//如果char1为空返回空指针
if(!i){s1.ch=nullptr;return 0;}
s1.ch=(char*)malloc(i* sizeof(char));
for (int j = 0; j <i ; ++j) {
s1.ch[j]=char1[j];
}
s1.length=i;
return 0;
}
//把s2和s3链接到s1中
Status Concat(HString &s1,HString s2,HString s3)
{
//if(s1.ch)free(s1.ch);
if(s2.length+s3.length<=0){s1.ch= nullptr;return 0;}
s1.ch=(char*)malloc((s2.length+s3.length)* sizeof(char));
for (int i = 0; i < s2.length; ++i) {
s1.ch[i]=s2.ch[i];
}
for (int j = 0; j < s3.length; ++j) {
s1.ch[j+s2.length]=s3.ch[j];
}
s1.length=s2.length+s3.length;
return 1;
}
//输出串
Status Printstr(HString &s1)
{
if(!s1.ch){ return 0;}
for (int i = 0; i < s1.length; ++i) {
cout<<s1.ch[i];
}
cout<<endl;
return 1;
}
//模式匹配
int Index(string S,string T,int pos)
{
int i=pos,j=0;
while (i<S.length()&&j<=T.length())
{
if(S[i]==T[j]){++i;++j;}
else{i=i-j+1;j=0;}
}
if(j>=T.length())return i-j+1;
else return 0;
}
int main()
{
string s1,s2;
HString S1,S2,S3;
cin>>s1;
cin>>s2;
char*s=trans(s1);
char*m=trans(s2);
Strassign(S1,s);
Strassign(S2,m);
int i=Index(s1,s2,0);
cout<<i;
}
|
还有一种bf算法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
//BF算法模式匹配
int Index(string S,string T,int pos)
{
int i=pos,j=0;
while (i<S.length()&&j<=T.length())
{
if(S[i]==T[j]){++i;++j;}
else{i=i-j+1;j=0;}
}
if(j>=T.length())return i-j+1;
else return 0;
}
|
剩余时间:4天返回7-2 jmu-ds-栈与队列-stack、queue与string小综合 (5分)
使用栈与队列逐个处理字符串中的每个字符
将line中的字符依次入栈，然后输出栈中元素个数与栈顶元素。
然后将栈中元素依次出栈并输出，出栈时将不等于x的字符依次入队列，以空格分隔。
输出队列元素个数，队头与队尾，以空格分隔。
最后输出队列中所有元素。
输入格式:
输入一个个字符串 输入一个字符
输出格式:
栈中元素个数 栈顶元素 栈中符合条件的元素(以空格分隔) 队列中元素个数
队头元素 队尾元素 队列中所有元素(以空格分隔)
输入样例:
输出样例:
1
2
3
4
| 11 t
tseTAsIsihT
8 t T
teTAIihT
|
可以用c++自带的stack和queue库来实现，省去自己写的麻烦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<iostream>
#include <stack>
#include <string>
#include <queue>
using namespace std;
int main()
{
stack<char>s;
string str;
queue<char>Q;
char x;
cin>>str;
for (int i = 0; str[i]!='\0'; ++i) {
s.push(str[i]);
}
cin>>x;
cout<<s.size()<<" "<<s.top()<<endl;
while(!s.empty()) {
cout<<s.top();
if(s.top()!=x)
{
Q.push(s.top());
}
s.pop();
}
cout<<endl;
cout<<Q.size()<<" "<<Q.front()<<" "<<Q.back()<<endl;
while (!Q.empty())
{
cout<<Q.front();
Q.pop();
}
}
|