面向对象的计算几何模板
Codeforces 600E. Lomsat gelral (线段树合并)

china-final F Mr. Panda and Fantastic Beasts (后缀自动机+字典序最小的最短路)

zjhl2 posted @ 2017年9月27日 21:01 in with tags 后缀自动机 最短路 后缀数组 最长公共子串 , 1404 阅读

题目链接:

http://codeforces.com/gym/101194

 

题意:

给n个字符串s1,s2......sn,问只在第一个字符串中出现的最短子串,多个答案输出字典序最小的子串。

 

思路:

把n个串用'z'+1连接起来建立后缀自动机,把s2到sn的母串上所有位置都标记cnt=1,如果parent树的子树和求完后,某个状态的cnt==0,那么所有能到达该状态的串都只在s1中出现过,于是求从root到这些cnt==0的状态的字典序最小的最短路就好了。

Time:420ms

 

#include<bits/stdc++.h>
using namespace std;

const int N=600005;

int tot,root,last;
int pa[N],deep[N],ch[N][27],cnt[N];
int newnode(int _deep)
{
	tot++;
	memset(ch[tot],0,sizeof(ch[tot]));
	deep[tot]=_deep;
	cnt[tot]=0;
	return tot;
}
void init()
{
	tot=0;
	root=newnode(0);
	last=root;
}
void insert(int w)
{
	int np=newnode(deep[last]+1);
	int u=last;
	while(u&&!ch[u][w]) ch[u][w]=np,u=pa[u];
	if (!u) pa[np]=root;
	else
	{
		int v=ch[u][w];
		if (deep[u]+1==deep[v]) pa[np]=v;
		else
		{
			int nv=newnode(deep[u]+1);
			memcpy(ch[nv],ch[v],sizeof(ch[v]));
			pa[nv]=pa[v]; pa[v]=pa[np]=nv;
			while(u&&ch[u][w]==v) ch[u][w]=nv,u=pa[u];
		}
	}
	last=np;
}
int sum[N],stk[N];
void topsort()
{
	for (int i=0;i<=deep[last];i++) sum[i]=0;
	for (int i=1;i<=tot;i++) sum[deep[i]]++;
	for (int i=1;i<=deep[last];i++) sum[i]+=sum[i-1];
	for (int i=1;i<=tot;i++) stk[sum[deep[i]]--]=i;
	for (int i=tot;i>=2;i--) cnt[pa[stk[i]]]+=cnt[stk[i]];
}

bool vis[N];
bool fst[N];
char s[N];
char st[N];
int pre[N];
int pc[N];

int bfs(int S)
{
	queue<int>Q;
	vis[S]=1;
	Q.push(S);
	while(!Q.empty())
	{
		int u=Q.front(); Q.pop();
		for (int w=0;w<26;w++)
		{
			int v=ch[u][w];
			if (v&&fst[v]&&!vis[v])
			{
				pre[v]=u;
				pc[v]=w;
				if (cnt[v]==0) return v;
				vis[v]=1;
				Q.push(v);
			}
		}
	}
	return -1;
}
int main()
{
	int t; scanf("%d",&t);
	for (int cas=1;cas<=t;cas++)
	{
		init();
        int n; scanf("%d",&n);
        scanf("%s",st+1);
		for (int i=1;st[i];i++) insert(st[i]-'a');
		for (int i=2;i<=n;i++)
		{
			scanf("%s",s+1);
			insert(26); cnt[last]=1;
			for (int j=1;s[j];j++)
				insert(s[j]-'a'),cnt[last]=1;
		}
		topsort();
		for (int i=1;i<=tot;i++) vis[i]=fst[i]=0;
		int now=1;
		for (int i=1;st[i];i++)
		{
			now=ch[now][st[i]-'a'];
			int tmp=now;
			while(tmp&&!fst[tmp]) fst[tmp]=1,tmp=pa[tmp];
		}
		printf("Case #%d: ",cas);
		int ret=bfs(1);
		if (ret!=-1)
		{
			int cnt=0;
			for (int i=ret;i!=1;i=pre[i]) s[++cnt]=pc[i]+'a';
			for (int i=cnt;i>=1;i--) printf("%c",s[i]);
			printf("\n");
		}
		else printf("Impossible\n");
	}
}

 

后缀自动机求字符串s1以i结尾的子串和s2到sn连接起来的串的最长公共子串,这个子串再向左延伸一个字符就是以i结尾的最短的只在s1中出现的子串。求出答案后暴力找字典序最小的串,要是答案太多可能会超时,然而数据没有卡这个时间。

Time:358ms

#include<bits/stdc++.h>
using namespace std;

const int N=600005;

int tot,root,last;
int pa[N],deep[N],ch[N][27],cnt[N];
int newnode(int _deep)
{
	tot++;
	memset(ch[tot],0,sizeof(ch[tot]));
	deep[tot]=_deep;
	cnt[tot]=0;
	return tot;
}
void init()
{
	tot=0;
	root=newnode(0);
	last=root;
}
void insert(int w)
{
	int np=newnode(deep[last]+1);
	int u=last;
	while(u&&!ch[u][w]) ch[u][w]=np,u=pa[u];
	if (!u) pa[np]=root;
	else
	{
		int v=ch[u][w];
		if (deep[u]+1==deep[v]) pa[np]=v;
		else
		{
			int nv=newnode(deep[u]+1);
			memcpy(ch[nv],ch[v],sizeof(ch[v]));
			pa[nv]=pa[v]; pa[v]=pa[np]=nv;
			while(u&&ch[u][w]==v) ch[u][w]=nv,u=pa[u];
		}
	}
	last=np;
}
int sum[N],stk[N];
void topsort()
{
	for (int i=0;i<=deep[last];i++) sum[i]=0;
	for (int i=1;i<=tot;i++) sum[deep[i]]++;
	for (int i=1;i<=deep[last];i++) sum[i]+=sum[i-1];
	for (int i=1;i<=tot;i++) stk[sum[deep[i]]--]=i;
	for (int i=tot;i>=2;i--) cnt[pa[stk[i]]]+=cnt[stk[i]];
}


char s[N];
char st[N];
int f[N];
bool cmp(int p1,int p2,int len)
{
	for (int i=0;i<len;i++)
		if (st[p1+i]!=st[p2+i]) return st[p1+i]<st[p2+i];
	return 1;
}
int main()
{
    int t; scanf("%d",&t);
    for (int cas=1;cas<=t;cas++)
    {
        init();
        int n; scanf("%d",&n);
        scanf("%s",st+1);
        for (int i=2;i<=n;i++)
        {
            scanf("%s",s+1);
            for (int j=1;s[j];j++)
                insert(s[j]-'a');
            insert(26);
        }
        int now=root,step=0;
        int ans=N;
        for (int i=1;st[i];i++)
		{
			while(now&&!ch[now][st[i]-'a']) now=pa[now];
			if (!now) now=1,step=0;
			else step=deep[now]+1,now=ch[now][st[i]-'a'];
			f[i]=step;
			if (i-f[i]>0) ans=min(ans,f[i]);
		}
        printf("Case #%d: ",cas);
        if (ans==N) printf("Impossible\n");
        else
		{
			int id=0;
			for (int i=1;st[i];i++)
				if (i-f[i]>0&&f[i]==ans)
				{
					if (id==0||cmp(i-ans,id-ans,ans+1)) id=i;
				}
			for (int i=id-f[id];i<=id;i++) printf("%c",st[i]);
			printf("\n");
		}
    }
}

 

后缀数组+二分答案,每次判断当前前缀相同的块里是否有s1的后缀并且没有其它串的后缀

Time:483ms

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=300005;

int a[N];
char s[N];
int pos,cut;
struct suffixarray
{
    int sa[N],rk[N],h[N];
    int cnt[N],sa2[N],rk2[N];
    int rlen[N];
    int n;
    bool cmp(int i,int j,int len)
    {
        if (rk2[i]==rk2[j]&&rk2[i+len]==rk2[j+len]) return 0;
        return 1;
    }
    void make(int *s,int len)
    {
        s[len+1]=-1;  //按情况修改
        n=len;
        int m=60000;   //按情况修改
        for (int i=0;i<=m;i++) cnt[i]=0;
        for (int i=1;i<=n;i++) cnt[s[i]]++;
        for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
        for (int i=n;i>=1;i--) sa[cnt[s[i]]--]=i;
        int k=1; rk[sa[1]]=1;
        for (int i=2;i<=n;i++)
        {
            if (s[sa[i]]!=s[sa[i-1]]) k++;
            rk[sa[i]]=k;
        }
        rk2[n+1]=0;
        for (int j=1;k<n&&j<=n;j*=2)
        {
            int tot=0;
            for (int i=n-j+1;i<=n;i++) sa2[++tot]=i;
            for (int i=1;i<=n;i++)
                if (sa[i]>j) sa2[++tot]=sa[i]-j;
            m=k;
            for (int i=1;i<=m;i++) cnt[i]=0;
            for (int i=1;i<=n;i++) cnt[rk[i]]++;
            for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
            for (int i=n;i>=1;i--) sa[ cnt[rk[sa2[i]]]-- ]=sa2[i];
            for (int i=1;i<=n;i++) rk2[i]=rk[i];
            k=1; rk[sa[1]]=1;
            for (int i=2;i<=n;i++)
            {
                if (cmp(sa[i],sa[i-1],j)) k++;
                rk[sa[i]]=k;
            }
        }
        for (int i=1;i<=n;i++)
        {
            if (rk[i]==1)
            {
                h[rk[i]]=0;  //这里很容易错
                continue;
            }
            k=h[rk[i-1]];
            if (k>0) k--;
            int j=sa[rk[i]-1];
            while(s[i+k]==s[j+k]) k++;
            h[rk[i]]=k;
        }
    }
    void show()
	{
		printf("\n");
		for (int i=1;i<=n;i++)
        {
            for (int j=sa[i];j<=n;j++)
             printf("%c",char(a[j]));
            printf(" %d\n",h[i]);
        }
	}
	int idx;
	bool check(int len)
	{
		bool hv1=0,hv2=0;
		for (int i=1;i<=n;i++)
		{
			if (h[i]<len)
			{
				if (hv1&&!hv2)
				{
					idx=sa[i-1];
					return 1;
				}
				hv1=hv2=0;
				if (rlen[sa[i]]>=len)
				{
					if (sa[i]<cut) hv1=1;
					else hv2=1;
				}
			}
			else
			{
				if (sa[i]<cut) hv1=1;
				else hv2=1;
			}
		}
		return 0;
	}
	void solve(int *s)
	{
		int tmp=n;
		for (int i=n;i>=1;i--)
		{
			if (s[i]>'z') tmp=i,rlen[i]=0;
			else rlen[i]=tmp-i;
		}
		int l=1,r=cut;
		while(l<r)
		{
			int mid=(l+r)/2;
			if (!check(mid)) l=mid+1;
			else r=mid;
		}
		if (l==cut) printf("Impossible\n");
		else
		{
			check(l);
			for (int i=idx;i<idx+l;i++)
				printf("%c",char(s[i]));
			printf("\n");
		}
	}
}SA;
int main()
{
    int t; scanf("%d",&t);
    for (int cas=1;cas<=t;cas++)
    {
        int n; scanf("%d",&n);
        pos=0;
        for (int i=1;i<=n;i++)
		{
			scanf("%s",s+1);
			for (int j=1;s[j];j++)
				a[++pos]=s[j];
			a[++pos]='z'+i;
			if (i==1) cut=pos;
		}
        SA.make(a,pos);
        printf("Case #%d: ",cas);
        //SA.show();
        SA.solve(a);
    }
}

Avatar_small
AP 1st Inter Botany 说:
2022年9月08日 00:48

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 1st Inter Botany Model Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter