我用字典树做的,最后两个点不是Re就是TLE,怎么办啊
查看原帖
我用字典树做的,最后两个点不是Re就是TLE,怎么办啊
178865
小林伊吕波楼主2021/4/2 18:46
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int n;
char alyson[3009],bob[3009];
int vis[2659006][26],top;
long long ans;
void biao(int l)
{
	int pos=0;
	int len=0;
	int father;
	for(int i=0;i<n;i++)
	{
		if(bob[l]==alyson[i])
		{
			if(len==0)
			{
			if(vis[0][alyson[i]-'a']==0)
			{
			ans++;
			vis[0][alyson[i]-'a']=ans;
			len=1;
			}
			father=vis[0][alyson[i]-'a'];
			len=1;
		}
		else{
			if(vis[father][alyson[i]-'a']==0)
			{
				ans++;
				vis[father][alyson[i]-'a']=ans;
				len++;
				father=ans;
				}
				else{
					len++;
			father=vis[father][alyson[i]-'a'];
				}
			}
			l++;
			if(l>=n) break;
		}
	}
}
int main()
{
	//freopen("block.in","r",stdin);
	//freopen("block.out","w",stdout);
	scanf("%d",&n);
	cin>>alyson>>bob;
	for(int i=0;i<n;i++)
	{
		biao(i);
	}
	//dfs(0,0,0);
	cout<<ans<<endl;
	return 0;
}
2021/4/2 18:46
加载中...