周报

踩过的字符串坑

2020年3月24日

1.Linux和windows下换行符不同，Linux下为\r\n，Windows下为\n，没掌握前尽量不要操作。

2.题目输入数据的最后一行末尾没有换行符，所以在读入时如果按字符读入，不用’\n’判断当前行是否结束，会造成TLE。

3.当多组输入时，用多少初始化多少，否则组数多内容少时，多次按可能会被使用最大空间来初始化会耗时过多，导致TLE。（绝大数的情况不出产生这种问题）

以下为多组输入时ac自动机的初始化的一种写法：

插入新字符串时：

if(!trie[now][id]){//当前结点不存在
	trie[now][id]=nn;//新建结点
	...
	memset(trie[nn],0,sizeof(trie[nn]));//初始化该结点
	...
}

当trie建成后，更新辅助数组：

while(~scanf("%d",&n)){
 	//初始化根结点
	memset(trie[0],0,sizeof(trie[0]));
	//读入模式串
    for(int i=1;i<=n;++i){
    	scanf(" %s",ss[i]);
    	insert(ss[i]);
    }
 	//根据使用的结点的多少来初始化辅助数组
    memset(fail,0,sizeof(int)*nn);
    memset(last,0,sizeof(int)*nn);
  	...
}

Views: 108

2条评论

发表评论