UVA 1401Remember the WordDp
7948 단어 word
dp가 이동하는 방정식:str[i->j]에 dp[i]+=dp[j+1]가 나타나면
그리고 사전 트리로str[i->j]가 나타났는지 조회합니다.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <map>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>
using namespace std;
char str[333333];
struct Node
{
int gaoguo ; struct Node* next[30];
}node[2111111];
const int mod= 20071027;
int len;
Node* newnode()
{
memset(&node[len],0,sizeof(node[len]));
return &node[len++];
}
Node *rt;
void Insert(string s,Node*root)
{
int len2=s.size();
for(int i= 0;i< len2;i++){
int cc=s[i]-'a';
if(!root->next[cc]){
root->next[cc]=newnode();
}
root=root->next[cc];
}
root->gaoguo=1;
}
int ask(string s,Node *root)
{
int len2=s.size();
for(int i=0;i<len2;i++){
int cc=s[i]-'a';
if(root->next[cc])
root=root->next[cc];
else return -1;
}
return root->gaoguo;
}
int len1;
int dp[333333];
char str1[333333];
int main()
{
int n;
int Icase= 0;
while(scanf("%s",str)!=EOF){
memset(dp,0,sizeof(dp));
len1=strlen(str);
scanf("%d",&n);
len=0; rt = newnode();
for(int i=0;i<n;i++){
scanf("%s",str1); Insert(str1,rt);
}
printf("Case %d: ",++Icase);
dp[len1]=1;
for(int i=len1-1;i>=0;i--){
string s="";
for(int j=i;j<len1;j++){
s+=str[j];
// cout<<s<<" "<<ask(s,rt)<<endl;
int cc=ask(s,rt);if(cc==-1) break;
if(cc==1) dp[i]+=dp[j+1],dp[i]%=mod;
}
}
cout<<dp[0]%mod<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java에서 Word를 암호로 보호된 PDF로 변환MS Word에서 계약 또는 법적 문서를 편집할 때 더 나은 전송 또는 인쇄를 위해 PDF로 변환해야 할 수 있습니다. 일부 기밀 문서의 경우 다른 사람이 스누핑하는 것을 방지하려면 지정된 사람만 이러한 문서에 액세...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.