POJ 1204
  QLtA9LK6PyNk 2023年11月02日 65 0


这个题查询的两个串有可能有公共前缀

trie树做法


#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
const int kind=26;
using namespace std;
char s[1010][1010];
int h[]={-1,-1,0,1,1,1,0,-1};
int g[]={0,1,1,1,0,-1,-1,-1};
int m,n,q,sum;
int xx[1010],yy[1010],zz[1010];

struct trie{
    struct trie * fail,*next[kind];
    int count,num;
};
struct trie * root;
void insert(char* str,int ii){
    int len=strlen(str),i,tem;
    struct trie *p,*q;
    p=root;
    for(i=0;i<len;i++){
        tem=str[i]-'A';
        if(p->next[tem]==NULL){
            q=(struct trie*)calloc(1,sizeof(struct trie));
            q->count=0;
            q->num=0;
            q->fail=NULL;
            memset(q->next,NULL,sizeof(q->next));
            p->next[tem]=q;
        }
        p=p->next[tem];
    }
    p->count=1;
    p->num=ii;
}
bool yes(int i,int j){
    if(i>=0 && j>=0 && i<n && j<m)
        return 1;
    return 0;
}
void query(int i,int j,int k){
    int tem,x,y,pp;
    struct trie* tmp=root,*p;
    x=i,y=j;
    for(pp=0;yes(i+pp*h[k],j+pp*g[k]);pp++){
        x=i+pp*h[k];
        y=j+pp*g[k];
        tem=s[x][y]-'A';
        if(tmp->next[tem]==NULL)
            return;
        tmp=tmp->next[tem];
        if(tmp->count){
            sum++;
            xx[tmp->num]=i;
            yy[tmp->num]=j;
            zz[tmp->num]=k;
            tmp->count=0;
        }
    }
}
void sea(){
    char str[2010];
    int i,j,k;
    sum=0;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++){
            for(k=0;k<8;k++){
                query(i,j,k);
                if(sum==q)return;
            }
        }
}
int main(){
    int i;
    char str[2010];
    root=(struct trie*)calloc(1,sizeof(struct trie));
    root->fail=NULL;
    root->count=0;
    root->num=0;
    memset(root->next,NULL,sizeof(root->next));

    scanf("%d %d %d",&n,&m,&q);
    for(i=0;i<n;i++)
        scanf("%s",s[i]);

    for(i=1;i<=q;i++){
        scanf("%s",str);
        insert(str,i);
    }
    sea();
    for(i=1;i<=q;i++){
        printf("%d %d %c\n",xx[i],yy[i],'A'+zz[i]);
    }
}





AC自动机做法



#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
const int kind=26;
using namespace std;
char s[1010][1010];
int h[]={-1,-1,0,1,1,1,0,-1};
int g[]={0,1,1,1,0,-1,-1,-1};
int m,n,q;
int xx[1010],yy[1010],zz[1010];
int len[1010];

struct trie{
	struct trie * fail,*next[kind];
	int count,num;
};
struct trie * root;
void insert(char* str,int ii){
	int len=strlen(str),i,tem;
	struct trie *p,*q;
	p=root;
	for(i=0;i<len;i++){
		tem=str[i]-'A';
		if(p->next[tem]==NULL){
			q=(struct trie*)calloc(1,sizeof(struct trie));
			q->count=0;
			q->num=0;
			q->fail=NULL;
			memset(q->next,NULL,sizeof(q->next));
			p->next[tem]=q;
		}
		p=p->next[tem];
	}
	p->count=1;
    p->num=ii;
}
void buildac(){
	int i;
	struct trie *p,*tem;
	queue<struct trie *>q;
	root->fail=NULL;
	q.push(root);
	while(!q.empty()){
		tem=q.front();
		q.pop();
		for(i=0;i<26;i++){
			if(tem->next[i]!=NULL){
				if(tem==root)
					tem->next[i]->fail=root;
				else{
					p=tem->fail;
					while(p!=NULL){
						if(p->next[i]!=NULL){
							tem->next[i]->fail=p->next[i];
							break;
						}
						p=p->fail;
					}
					if(p==NULL)
						tem->next[i]->fail=root;
				}
				q.push(tem->next[i]);
			}
		}
	}
}
void query(int x,int y,int k){
	int tem;
	struct trie* tmp=root,*p;
	for(;s[x][y]!='\0';x+=h[k],y+=g[k]){
		tem=s[x][y]-'A';
		while(tmp->next[tem]==NULL && tmp!=root)
			tmp=tmp->fail;
		tmp=tmp->next[tem];
		if(tmp==NULL)
			tmp=root;
		p=tmp;
		while(p!=root){
            if(p->count==1){
                p->count=0;
                xx[p->num]=x-h[k]*(len[p->num]-1)-1;
                yy[p->num]=y-g[k]*(len[p->num]-1)-1;
                zz[p->num]=k;
            }
			p=p->fail;
		}
	}
}

void acwork(){
    int i;
    for(i=1;i<=n;i++){
        query(i,1,1),query(i,1,2),query(i,1,3);
        query(i,m,5),query(i,m,6),query(i,m,7);
    }
    for(i=1;i<=m;i++){
        query(1,i,3),query(1,i,4),query(1,i,5);
        query(n,i,1),query(n,i,0),query(n,i,7);
    }
}
int main(){
	int i;
	char str[2010];
    root=(struct trie*)calloc(1,sizeof(struct trie));
    root->fail=NULL;
    root->count=0;
    root->num=0;
    memset(root->next,NULL,sizeof(root->next));

    memset(s,'\0',sizeof(s));
    scanf("%d %d %d",&n,&m,&q);
    for(i=1;i<=n;i++)
        scanf("%s",&s[i][1]);

    for(i=1;i<=q;i++){
        scanf("%s",str);
        len[i]=strlen(str);
        insert(str,i);
    }
    buildac();
    acwork();
    for(i=1;i<=q;i++){
        printf("%d %d %c\n",xx[i],yy[i],'A'+zz[i]);
    }
}



【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

上一篇: 一道趣题(catalan数) 下一篇: poj 1743
  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  QLtA9LK6PyNk   2023年11月02日   56   0   0 2010Hive随机数
  QLtA9LK6PyNk   2023年11月02日   66   0   0 queryinsertstructnull2010
QLtA9LK6PyNk
作者其他文章 更多

2023-11-02

2023-11-02

2023-11-02

2023-11-02

2023-11-02

2023-11-02

2023-11-02

2023-11-02