[SPOJ 413] | Eurce's Blog

trie图

题意：输入一个r*c的字符矩阵，以及w个单词，每个单词会在字符矩阵中以某种方式出现一次。这里“某种方式”是指单词起始位置任意，其余部分沿横竖斜共8个方向中的一种直列排布。要求的就是各个单词以“哪种方式”出现。

如果是单模式匹配，可以采用滚动hash、trie树、kmp等等。但这里是多模式匹配，因此需要用到trie图，也即有穷自动机（DFA）。建图的方式参考了王赟的《Trie 图的构建、活用与改进》。基本做法是，根据w个单词建好trie树后，补全树上尚未定义的状态转移即可得到trie图。其中关键思想在于，若从某结点出发的目标字符对应状态在树中不存在，则指向其后缀结点的目标字符子结点。这里某结点的后缀结点指的是，该结点对应字符串去掉头字符后在trie树上的匹配终结点，具体可以根据该结点的父结点的后缀结点计算得到。可以发现，某结点的深度必定是大于其后缀结点的，因此，可以通过BFS的方式依次补齐trie树上各层结点的状态转移来得到trie图。而对于匹配是否成功，存在一个定理：某结点能匹配成功当且仅当其后缀结点能匹配成功。

回到题目，由于题目本身已经明确每个单词刚好仅在原字符矩阵出现一次。因此枚举8个方向，依次从各起始结点在trie图上作状态转移，每当遇到终结点时记录对应字符串的匹配信息即可。

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

int r,c,w,root,el,x[1001],y[1001],tk[1001],tl[1001];
char s[1000][1001],t[1001];
int dm[8][2]={-1,0, -1,1, 0,1, 1,1, 1,0, 1,-1, 0,-1, -1,-1};

struct E
{
    int b,c,fa,sp,p[26];
}e[1000000];

void mk(int ti)
{
    int i,j,k,l;
    for(i=0,l=root;t[i];i++)
    {
        if(!e[l].p[t[i]-'A'])
        {
            e[l].p[t[i]-'A']=el++;
            e[e[l].p[t[i]-'A']].c=t[i]-'A';
            e[e[l].p[t[i]-'A']].fa=l;
        }
        l=e[l].p[t[i]-'A'];
    }
    e[l].b=ti;
}

void init()
{
    int i,j,k,l;
    el=0;
    memset(e,0,sizeof e);
    root=el++;
    for(i=0;i<r;i++)
        scanf("%s",s[i]);
    for(i=1;i<=w;i++)
    {
        scanf("%s",t);
        tl[i]=strlen(t);
        mk(i);
    }
    queue<int>Q;
    Q.push(root);
    while(!Q.empty())
    {
        i=Q.front(); Q.pop();
        for(l=0;l<26;l++)
            if(e[i].p[l])
                Q.push(e[i].p[l]);
        if(e[i].fa!=root)
            e[i].sp=e[e[e[i].fa].sp].p[e[i].c];
        for(l=0;l<26;l++)
            if(!e[i].p[l])
                e[i].p[l]=e[e[i].sp].p[l];
        e[i].b|=e[e[i].sp].b;
    }
}

inline bool chk(int i,int j)
{
    return i>-1&&i<r&&j>-1&&j<c;
}

void calc(int i,int j,int k)
{
    int l=root;
    while(chk(i,j))
    {
        l=e[l].p[s[i][j]-'A'];
        if(e[l].b)
        {
            x[e[l].b]=i-dm[k][0]*(tl[e[l].b]-1);
            y[e[l].b]=j-dm[k][1]*(tl[e[l].b]-1);
            tk[e[l].b]=k;
        }
        i+=dm[k][0];
        j+=dm[k][1];
    }
}

void solve()
{
    int i,j;
    for(i=r-1,j=0;j<c;j++)
        calc(i,j,0);

    for(i=0,j=0;i<r;i++)
        calc(i,j,1);
    for(i=r-1,j=1;j<c;j++)
        calc(i,j,1);

    for(i=0,j=0;i<r;i++)
        calc(i,j,2);

    for(i=0,j=c-1;j;j--)
        calc(i,j,3);
    for(i=0,j=0;i<r;i++)
        calc(i,j,3);

    for(i=0,j=0;j<c;j++)
        calc(i,j,4);

    for(i=0,j=0;j<c;j++)
        calc(i,j,5);
    for(i=1,j=c-1;i<r;i++)
        calc(i,j,5);

    for(i=0,j=c-1;i<r;i++)
        calc(i,j,6);

    for(i=0,j=c-1;i<r;i++)
        calc(i,j,7);
    for(i=r-1,j=c-2;j>-1;j--)
        calc(i,j,7);
    for(i=1;i<=w;i++)
        printf("%d %d %c\n",x[i],y[i],'A'+tk[i]);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d%d",&r,&c,&w))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include<queue>

#include<cstdio>

#include<cstring>

using namespace std;

int r,c,w,root,el,x[1001],y[1001],tk[1001],tl[1001];

char s[1000][1001],t[1001];

int dm[8][2]={-1,0, -1,1, 0,1, 1,1, 1,0, 1,-1, 0,-1, -1,-1};

struct E

{

int b,c,fa,sp,p[26];

}e[1000000];

void mk(int ti)

{

int i,j,k,l;

for(i=0,l=root;t[i];i++)

{

if(!e[l].p[t[i]-'A'])

{

e[l].p[t[i]-'A']=el++;

e[e[l].p[t[i]-'A']].c=t[i]-'A';

e[e[l].p[t[i]-'A']].fa=l;

}

l=e[l].p[t[i]-'A'];

}

e[l].b=ti;

}

void init()

{

int i,j,k,l;

el=0;

memset(e,0,sizeof e);

root=el++;

for(i=0;i<r;i++)

scanf("%s",s[i]);

for(i=1;i<=w;i++)

{

scanf("%s",t);

tl[i]=strlen(t);

mk(i);

}

queue<int>Q;

Q.push(root);

while(!Q.empty())

{

i=Q.front(); Q.pop();

for(l=0;l<26;l++)

if(e[i].p[l])

Q.push(e[i].p[l]);

if(e[i].fa!=root)

e[i].sp=e[e[e[i].fa].sp].p[e[i].c];

for(l=0;l<26;l++)

if(!e[i].p[l])

e[i].p[l]=e[e[i].sp].p[l];

e[i].b|=e[e[i].sp].b;

}

inline bool chk(int i,int j)

{

return i>-1&&i<r&&j>-1&&j<c;

}

void calc(int i,int j,int k)

{

int l=root;

while(chk(i,j))

{

l=e[l].p[s[i][j]-'A'];

if(e[l].b)

{

x[e[l].b]=i-dm[k][0]*(tl[e[l].b]-1);

y[e[l].b]=j-dm[k][1]*(tl[e[l].b]-1);

tk[e[l].b]=k;

}

i+=dm[k][0];

j+=dm[k][1];

}

void solve()

{

int i,j;

for(i=r-1,j=0;j<c;j++)

calc(i,j,0);

for(i=0,j=0;i<r;i++)

calc(i,j,1);

for(i=r-1,j=1;j<c;j++)

calc(i,j,1);

for(i=0,j=0;i<r;i++)

calc(i,j,2);

for(i=0,j=c-1;j;j--)

calc(i,j,3);

for(i=0,j=0;i<r;i++)

calc(i,j,3);

for(i=0,j=0;j<c;j++)

calc(i,j,4);

for(i=0,j=0;j<c;j++)

calc(i,j,5);

for(i=1,j=c-1;i<r;i++)

calc(i,j,5);

for(i=0,j=c-1;i<r;i++)

calc(i,j,6);

for(i=0,j=c-1;i<r;i++)

calc(i,j,7);

for(i=r-1,j=c-2;j>-1;j--)

calc(i,j,7);

for(i=1;i<=w;i++)

printf("%d %d %c\n",x[i],y[i],'A'+tk[i]);

}

int main()

{

scanf("%*d");

while(~scanf("%d%d%d",&r,&c,&w))

{

init();

solve();

}

return 0;

}

内存开小了RE了一次，然后AC的程序也很慢……不过总体来说还算是挺顺利的。

ps：唠叨点题外话，很多字符串算法貌似都只对英语有效呢，使用大数组来余存储匹配信息的做法对于中文或其他多字符语言却不太适用。其他的领域，包括分词、语法分析等等，貌似也是英语比较容易处理。会有那么一天，由于技术极致发展催生出的工业需求，反过来局限人类文明的进步吗？