Criska

字符串类型问题

• 分类: 字符串, KMP, string • 标签: KMP, string, 字符串

1.KMP字符串匹配

求匹配字符的KMP算法，详情移步Franky博客O(∩_∩)O~~
放一个模板上来

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=50;
int la,lb,next[N];
char a[N],b[N];
inline void qiunext()
{
	next[0]=-1;
	for(int i=2,j=0;i<=lb;++i,++j)
	{
		while(j!=-1&&b[i]!=b[j+1]) j=next[j];
		next[i]=j+1;
	}
}
inline void kmp()
{
	for(int i=1,j=0;i<=la;++i,++j)
	{
		while(j!=-1&&a[i]!=b[j+1]) j=next[j];
		if(j==lb-1) printf("%d ",i-j);
	}
}
int main()
{
	scanf("%s%s",a+1,b+1);
	la=strlen(a+1);
	lb=strlen(b+1);
	qiunext();
	kmp();
	return 0;
}

2.JOIOJI

用J[X] ,O[X], I[X]表示前X个数中J,O,I的个数，那么假设从X到Y的字符串条件符合，可以想到的是，前Y个字符的J,O,I之差必定和前X个字符的J,O,I之差相等，并且我们是从前往后搜的，前X个字符的值已经计算过了，所以我们可以用map来记录位置，每次判断一下J,O,I之差相等的字符串的位置（没有则是0），这样时间复杂度就能减少到n*log（n）了，因为map一次计算为log(n)。
map的具体使用方法在白皮本关联式容器一节
附上代码：

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
#include<iostream>
#include<cstdio>
#include<map>
#include<cctype>
#include<cstring>
using namespace std;
typedef pair<int,int>p;
#define ma make_pair
#define N 200010
char a[N];
int l;
map<p,int>m;
int main()
{
	//freopen("noioni.in","r",stdin);
	//freopen("noioni.out","w",stdout);
	scanf("%d",&l);
	scanf("%s",a+1);
	m[ma(0,0)]=0;
	int nn=0,oo=0,ii=0,ans=0;
	for(int i=1;i<=l;++i)
	{
		if(a[i]=='J') jj++;
		if(a[i]=='O') oo++;
		if(a[i]=='I') ii++;
		if(m.count(ma(jj-oo,jj-ii)))
		{
			ans=max(ans,i-m[ma(jj-oo,nn-ii)]);
		}
		else m[ma(nn-oo,jj-ii)]=i;
	}	
	printf("%d",ans);
	return 0;
}

3.单词分类

get了用string排序的方法

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,c,ls,cnt=1;
string s[10010];
int comp(const char & a,const char & b)
{
	if(a>b) return b;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		cin>>s[i];
		sort(s[i].begin(),s[i].end());
	}
	sort(s+1,s+n+1);
	for(int i=2;i<=n;++i)
	{
		if(s[i]!=s[i-1]) cnt++;
	}
	printf("%d",cnt);
	return 0;
}

4.小W算数

【问题描述】
投我以木桃，报之以琼瑶~
得到树的小 M 非常开心，回送小 W一个名单，名单背后藏着甜蜜的秘密！名单里名字都
很奇怪，并且很多捣乱的同学把自己等价名字写很多次。
现在小M告诉小 W 名字的等价方式：

  1. 选择一个名字 S
  2. 选择S的一个偶数长前缀T
  3. 把 T反转，得到新的 S
    例如：‘wrhmly’->‘rwhmly’->‘mhwrly’->‘hmwrly’
    为了使秘密更容易浮现，等价可传递：A和B等价，B 和C 等价，那么A 和C 也等价。
    小 W 需要每次取两个等价的名字，把它们去掉，求出最后剩下多少名字。

【输入格式】
第一行一个整数N，代表名字个数。
第 2到 N+1行，每行一个字符串表示一个名字。

【输出格式】
一行一个整数，表示剩下名字个数。

【输入输出样例】

list.in

20
iprlzgukfggzg
bmhxvjbrtkbxy
khapjiabbny
nqlwgmcyvdikt
nxromtvtpug
leealcapovm
ushnxwjczczbmd
bwhykzupcux
xrlboyuwlnsp
bbjoketeheezfs
dxfztrldomjqkv
dkbktqdtgfujcut
zfybzyuxgpnt
ffmsldrdftode
vopuufksxd
pqhbsiujwda
yhwbkzupcux
hkbabnapjiy
zqsqefrrzehtxn
yovinyguyudmv

list.out
16

list.in
7
esprit
wrhmly
jitui
tujii
mhwrly
hmwrly
tirpse

list.out
1

  • 先来吐槽 这个出题人是多喜欢诗经………每一题都发一碗狗粮……

  • 首先有一个结论：如果串的长度为偶数，把2k-1和2k 位看成一组，若干转换之后，这些组之间的顺序可以任意改变（即可以变成它们的全排列中任意一个），在此前提下，每组内部的两个字符的顺序也可以随便改变。

  • 所以，我们需要的是两位两位比较字符串，比如ab既和ab匹配，又和ba匹配（string大法好）

附上我丑陋的代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,tot;
string a[100];
inline int pipei(string x,string y)
{
	if(x==y) return 1;
	int m=x.length();
	for(int i=0;i<m;i+=2)
	{
		for(int j=0;j<m;++j)
		{
			if(x[i]==y[j])
			{
				if(j%2)
				{
					if(x[i+1]==y[j-1])
					{
						x[i]=x[i+1]=y[j]=y[j-1]='0';
					}
				}
				else
				{
					if(x[i+1]==y[j+1])
					{
						x[i]=x[i+1]=y[j]=y[j+1]='0';
					}
				}
			}
		}
	}
	if(x==y) return 1;
	else return 0;
}
int main()
{
	freopen("list.in","r",stdin);
	freopen("list.out","w",stdout);
	scanf("%d",&n);
	tot=n;
	string bijiao="0";
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n-1;++i)
	{
		int jilu=0;
		for(int j=i+1;j<=n;++j)
		{
			if(a[i]!=bijiao&&a[j]!=bijiao&&a[i].length()==a[j].length())
			{
				if(pipei(a[i],a[j]))
				{
					a[i]="0";
					a[j]="0";
					tot-=2;
					jilu=1;
					break;
				}
				
			}
			if(jilu==1) break;
		}
	}
	printf("%d",tot);
	return 0;
}

5.【模板】字符串哈希

  • 实话实说，我不会用哈希表，所以让我们来学习一下naive同学交给我们的神奇的map算法，轻松ac，至于哈希…………等我学会了再来补上= =
  • map实际上就是一个映射，具体请移步百度百科或者第二道例题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
using namespace std;
const int N=20000;
map<string,int>p;
int n;
string s[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		cin>>s[i];
		p[s[i]]=1;
	}
	printf("%d",p.size());
	return 0;
}

6.统计单词数

这可是普及组的题啊！！！
我调了好久啊！！
心疼普及组的同学，同时也深深地怀疑我的智商= =

  • 这道题本质上其实还是一道kmp，只是我们要将数组进行转化
  • 将‘a’变为‘空格a空格 ‘
  • 将‘b’变为‘空格b空格 ‘
    然后用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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int N=2000000;
int la,lb,cnt=0,next[N],mark;
char a[N],b[N];
inline void getnext()
{
	next[0]=-1;
	for(int i=2,j=0;i<=la;++i,++j)
	{
		while(j!=-1&&a[i]!=a[j+1]) j=next[j];
		next[i]=j+1;
	}
}
inline int kmp()
{
	for(int i=1,j=0;i<=lb+2;++i,++j)
	{
		while(j!=-1&&b[i]!=a[j+1]) j=next[j];
		if(j==la-1)
		{
			if(mark==0)
			{
				mark=i-j;
				cnt++;
			}
			else
			{
				cnt++;
			}
		} 
	}
}
int main()
{
	gets(a+2);
	la=strlen(a+2);
	gets(b+2);
	lb=strlen(b+2);
	//cout<<la<<endl<<lb<<endl;
	for(int i=2;i<=la+2;++i)
	{
		if('A'<=a[i]&&a[i]<'a') a[i]=a[i]+'a'-'A';
	}
	for(int i=2;i<=lb+2;++i)
	{
		if('A'<=b[i]&&b[i]<'a') b[i]=b[i]+'a'-'A';
	}
	a[1]=' ';b[1]=' ';
	if(a[la+1]!=' ')
	{
		a[la+2]=' ';
		la+=2;
	}
	else la++;
	if(b[lb+2]!=' ')
	{
		b[lb+2]=' ';
		lb+=2;	
	}
	else lb++;
	//for(int i=1;i<=lb;++i)
	//cout<<b[i];
	getnext();
	kmp();
	if(cnt!=0) printf("%d %d",cnt,mark-1);
	else printf("-1");
	return 0;
}

7.子串

DP+滚动数组，调的有点恶心……
但是只要理解f和g数组分别代表什么就可以了，引用了menci大神的解析 $\downarrow$

代码如下

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
#include<iostream>
#include<cstdio>
using namespace std;
const int p=1000000007;
int la,lb,K,f[3][201][201],g[3][201][201];
char a[1010],b[250];
int main()
{
	freopen("substring.in","r",stdin);
	freopen("substring.out","w",stdout);
	scanf("%d%d%d",&la,&lb,&K);
	scanf("%s",a+1);
	scanf("%s",b+1);
	f[0][0][0]=g[0][0][0]=1;
	for(int i=1;i<=la;++i)
	{
		f[i%2][0][0]=1;
		g[i%2][0][0]=1;
		for(int j=1;j<=lb;++j)
		{
			for(int k=1;k<=K;++k)
			{
				if(a[i]==b[j])
				{					
					f[i%2][j][k]=f[(i-1)%2][j-1][k];
					f[i%2][j][k]+=g[(i-1)%2][j-1][k-1];
					f[i%2][j][k]%=p;
					g[i%2][j][k]=(g[(i-1)%2][j][k]+f[i%2][j][k])%p;
				}
				else
				{
					f[i%2][j][k]=0;
					g[i%2][j][k]=g[(i-1)%2][j][k]%p;
				}
			}
		}
	}
	printf("%d",g[la%2][lb][K]%p);
	return 0;
}

8.String Master

所谓最长公共子串，比如串A：“abcde”，串B：“jcdkl”，则它们的最长公共子串为串“cd”，即长
度最长的字符串，且在两个串中都作为连续子串出现过。
给定两个长度都为n 的字符串，对于字符串大师的你来说，求它们的最长公共子串再简单不过了。
所以现在你有k 次修改机会，每次你可以选择其中某个串的某个位置，将其修改成任意字符。
你需要合理使用这k 次修改机会，使得修改之后两个串的最长公共子串最长。相信对于字符串大师
的你来说，这个问题也难不倒你。

Input
第一行包含两个整数n; k，分别表示字符串的长度和修改次数。
第二行包含一个长度为n 的仅由小写字符构成的字符串S。
第三行包含一个长度为n 的仅由小写字符构成的字符串T。

Output
输出一行一个整数，即修改完毕之后两个串的最长公共子串的长度。

Examples

master.in
5 0
abcde
jcdkl

5 2
aaaaa
ababa

master.out

2

5

枚举它的答案的可能性，然后再通过枚举来check是否成立，总的来说就是个暴力中的暴力（然而我用了DP【手动再见】）
代码：

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
#include<iostream>
#include<cstdio>
using namespace std;
int n,K,cnt,maxx=0;
char a[301],b[301];
inline int check(int x)
{
	for(int i=0;i<=n-x;++i)
	{
		for(int j=0;j<=n-x;++j)
		{
			cnt=0;
			for(int p=1;p<=x;++p)
			{
				if(a[p+i]!=b[p+j])
				cnt++;
			}
			if(cnt<=K) return 1;
		}
	}
	return 0;
}
int main()
{
	freopen("master.in","r",stdin);
	freopen("master.out","w",stdout);
	scanf("%d%d",&n,&K);
	scanf("%s",a+1);
	scanf("%s",b+1);
	for(int i=1;i<=n;++i)
	{
		cnt=0;
		if(check(i))
		{
			maxx=i;
		}
		else break;
	}	
	printf("%d",maxx);
	return 0;
}