【题解】Fuzzy Google Suggest(UVA1462)

题意

给定一个字符串集合，有n次搜索，每次有一个整数x和一个字符串，表示可以对字符串进行x次修改，

包括增加、修改和删除一个字符，问修改后的字符串可能是字符集中多少个字符串的前缀。

思路

简单题。主要是觉得模糊匹配挺有意思的，虽然跟Google没啥关系

首先对给出的字符串集建 Trie。对于每一次搜索操作，在 Trie 上进行两次 dfs（算上清理是3次，因为数据范围三百万不可能 memset ，代码中将计算贡献和清除一起写了）

第一次 dfs 对于搜索串进行处理，如果匹配那么直接搜索，否则减少一次剩余修改次数并继续搜索。这个过程中，为了计算贡献需要打 tag，如果是路径上经过的 Trie 节点就标记为1，如果是结尾就标记为2.

第二次 dfs 对tag数组清除，并累加第一次出现2的位置的贡献。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=3e6+10;

int n;

char str[21];

struct Trie

{

        int siz,g[N][26],val[N],vis[N];

        int dep,ans;

        char s[21];

        void init()

        {

                siz=1; val[0]=0; memset( g[0],0,sizeof(g[0]) );

        }

        void dfs( int p,int len,int x )

        {

                if ( x<0 ) return;

                if ( vis[p]==0 ) vis[p]=1;

                if( len==dep ) { vis[p]=2; return; }

                int ch=s[len]-'a';

                if ( g[p][ch] ) dfs( g[p][ch],len+1,x );

                dfs( p,len+1,x-1 );

                for ( int i=0; i<26; i++ )

                        if ( g[p][i] ) dfs( g[p][i],len,x-1 ),dfs( g[p][i],len+1,x-1 );

        }

        void clear( int p,int flag )

        {

                if ( vis[p]==0 ) return;

                if ( flag && vis[p]==2 ) ans+=val[p],flag=0;

                for ( int i=0; i<26;  i++ )

                        if ( g[p][i] ) clear( g[p][i],flag );

                vis[p]=0;

        }

        int calc( char *str,int x )

        {

                ans=0; dep=strlen(str); strcpy( s,str );

                dfs( 0,0,x ); clear( 0,1 );

                return ans;

        }

        void insert( char *str )

        {

                int p=0,n=strlen(str);

                for ( int i=0; i<n; i++ )

                {

                        int ch=str[i]-'a';

                        if ( g[p][ch]==0 )

                        {

                                val[siz]=0; memset( g[siz],0,sizeof(siz) );

                                g[p][ch]=siz++;

                        }

                        p=g[p][ch]; val[p]++;

                }

        }

}tr;

int main()

{

        while ( scanf( "%d",&n )==1 )

        {

                tr.init();

                for ( int i=0; i<n; i++ )

                        scanf( "%s",str ),tr.insert(str);

                scanf( "%d",&n );

                while ( n-- )

                {

                        int x; scanf( "%s%d",str,&x );

                        printf( "%d\n",tr.calc(str,x) );

                }

        }

}

巴特西

【题解】Fuzzy Google Suggest(UVA1462)

题意

思路

代码

最新文章

热门文章