题目描述
有一天,小赵正在愉快的敲代码,小钱说:“小赵,你这个变量的名字取的可读性不行啊,我都不知道哪里到哪里代表什么意思。”
小赵不服气的说:“那你给我一组变量名,我保证我的变量名可以拆开,并且拆开的每一个变量名都在你这组变量名中出现”。
现在小钱提供了一组不含重复变量名的列表,你能判断小赵的变量名是否能够拆分为多个小钱提供的变量名吗,能则输出True,不能则输出False。
说明:可以重复使用小钱提供的变量名,输入变量名长度均不超过10000,变量名个数不超过10000,所有变量名总字符长度不超过106。
输入样例
thisisadog
this thisis is a dog
输出样例
True
算法1
(字符串hash) $O(n^2)$
1.
将string映射成unsigned long long
对于字符串val,长度为n,其hash公式为
Hashval = ( val[ 1 ] * P ^ ( n - 1 ) + val[ 2 ] * P ^ ( n - 2 ) … + val[ n ] * P ^ 0 ) % Q;
Q为2^64,可以避免mod运算
子串val[ l ~ r ] 求法
h[ i ] 表示 val[ 1 ~ r ]的hash值
Hashvallr = h[ r ] - h[ l - 1 ] * P ^ ( r - l + 1 )
将h[ l - 1 ]的值左移 r - l + 1 位,这样使得求得的子串的值与 hash公式的值等价
2.
dp[ i ]表示前i个字符能否分割
dp[ i ] |= ( dp[ j - 1 ] && val[ j - i ]能被找到 )
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 10010, P = 131;
char str[ N ], word[ N ];
ull h[ N ], p[ N ];
unordered_set< ull > s;
int f[ N ];
ull get( int l, int r )
{
return h[ r ] - h[ l - 1 ] * p[ r - l + 1 ];
}
int main()
{
scanf( "%s", str + 1 );
int n = strlen( str + 1 );
p[ 0 ] = 1;
for( int i = 1; i <= n; i ++ )
{
h[ i ] = h[ i - 1 ] * P + str[ i ];
p[ i ] = p[ i - 1 ] * P;
}
while( scanf( "%s", word + 1 ) != - 1 )
{
ull tot = 0;
for( int i = 1; word[ i ]; i ++ ) tot = tot * P + word[ i ];
s.insert( tot );
}
f[ 0 ] = 1;
for( int i = 1; i <= n; i ++ )
for( int j = i; j; j -- )
{
if( f[ j - 1 ] && s.count( get( j, i ) ) )
{
f[ i ] = 1;
break;
}
}
if( f[ n ] ) printf( "True" );
else printf( "False" );
return 0;
}
算法2
(trie树) $O(n^2)$
将字符串反转后插入Trie树中
对原本字符串长度由大到小进行遍历,然后更新dp值
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int Max = 1e5 * 5;
int dp[ 10010 ];
struct Trie
{
int ch[ Max ][ 26 ];
int val[ Max ];
int tot;
void Init()
{
memset( ch, 0, sizeof( ch ) );
memset( val, 0, sizeof( val ) );
tot = 1;
}
void Insert( string word )
{
int root = 0;
for( auto x: word )
{
int Index = x - 'a';
if( !ch[ root ][ Index ] ) ch[ root ][ Index ] = tot ++;
root = ch[ root ][ Index ];
}
val[ root ] = 1;
}
void Search( string word, int i )
{
int root = 0;
int tmp = i;
for( auto x: word )
{
int Index = x - 'a';
if( !ch[ root ][ Index ] ) return;
root = ch[ root ][ Index ];
tmp --;
if( val[ root ] ) dp[ i ] |= dp[ tmp ];
}
return;
}
};
string s1, s2, s3;
Trie t;
int main()
{
cin >> s1;
t.Init();
while( cin >> s2 )
{
reverse( s2.begin(), s2.end() );
t.Insert( s2 );
}
int n = s1.length();
dp[ 0 ] = 1;
for( int i = 1; i <= n; i ++ )
{
s3 = s1.substr( 0, i );
reverse( s3.begin(), s3.end() );
t.Search( s3, i );
}
cout << ( dp[ n ] == 1 ? "True" : "False" ) << endl;
return 0;
}
请问第一种方法P的取值有什么讲究么
有的,特定的几个数,<<算法竞赛进阶指南>>有讲到
java 用这个方法过不了、、还是超时
C++可以过,但第二种方法的耗时是第一种的4倍,可能不是正解的缘故吧