HDU 4416 Good Article Good sentence
제목: 문자열 S 와 일련의 문자열 T1 ~ Tn 을 주 고 S 에서 몇 개의 다른 문자열 이 T1 ~ Tn 의 임의의 문자열 이 아 닌 하위 문자열 을 만족 시 키 는 지 물 어 봅 니 다.
사고: 우 리 는 먼저 S 의 접두사 자동 동 기 를 구성 한 다음 에 모든 Ti 를 S 의 SAM 에 일치 시 킵 니 다. LCS 와 유사 합 니 다. S 의 모든 상태 에 하나의 변 수 를 기록 한 deep 는 T1 ~ Tn 을 표시 합 니 다. 이 상태 에서 일치 할 수 있 는 최대 길 이 는 얼마 입 니까? 모든 Ti 를 일치 시 킨 후에 우 리 는 S 의 SAM 을 토폴로지 로 정렬 하고 아래 에서 위로 모든 상태의 deep 를 업데이트 합 니 다.이 상태 에서 몇 개의 문자열 이 문제 의 요 구 를 만족 시 키 는 지 동시에 계산한다.구체 적 인 절 차 는 다음 과 같다.
1: 현재 상태 에 대해 p 로 설정 하고 p 의 par 를 q 로 설정 하면 q - > deep 을 q - > deep 과 p - > deep 의 큰 값 으로 업데이트 합 니 다.
2: p - > deep < p - > val 의 경우 상태 p 에서 길이 가 p - > deep + 1 ~ p - > val 의 하위 문자열 은 T1 ~ Tn 의 임의의 문자열 의 하위 문자열 이 아니 므 로 답 에 p - > val - p - > deep 을 더 합 니 다.그렇지 않 으 면 상태 p 의 모든 문자열 이 요 구 를 만족 시 키 지 못 하고 건 너 뛰 면 됩 니 다.
(p - > deep = = 0 을 주의 하면 상태 p 의 모든 하위 문자열 이 문제 의 요 구 를 만족 시 키 는 것 을 나타 낸다. 그러나 답 은 p - > val - 0 을 추가 하 는 것 이 아니 라 p - > val - p - > par - > val 을 추가 하 는 것 이다. 이것 은 상태 p 의 문자열 개 수 를 나타 내 므 로 p - > deep = 0 에 대해 서 는 특별 처리 해 야 한다)
마지막 으로 답 을 출력 하면 됩 니 다.
Good Article Good sentence
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2152 Accepted Submission(s): 602
Problem Description
In middle school, teachers used to encourage us to pick up pretty sentences so that we could apply those sentences in our own articles. One of my classmates ZengXiao Xian, wanted to get sentences which are different from that of others, because he thought the distinct pretty sentences might benefit him a lot to get a high score in his article.
Assume that all of the sentences came from some articles. ZengXiao Xian intended to pick from Article A. The number of his classmates is n. The i-th classmate picked from Article Bi. Now ZengXiao Xian wants to know how many different sentences she could pick from Article A which don't belong to either of her classmates?Article. To simplify the problem, ZengXiao Xian wants to know how many different strings, which is the substring of string A, but is not substring of either of string Bi. Of course, you will help him, won't you?
Input
The first line contains an integer T, the number of test data.
For each test data
The first line contains an integer meaning the number of classmates.
The second line is the string A;The next n lines,the ith line input string Bi.
The length of the string A does not exceed 100,000 characters , The sum of total length of all strings Bi does not exceed 100,000, and assume all string consist only lowercase characters 'a' to 'z'.
Output
For each case, print the case number and the number of substrings that ZengXiao Xian can find.
Sample Input
3
2
abab
ab
ba
1
aaa
bbb
2
aaaa
aa
aaa
Sample Output
Case 1: 3
Case 2: 3
Case 3: 1
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define prt(k) cout<<#k"="<<k<<endl;
#define ll long long
const int N=200200;
struct Node
{
Node *ch[26],*f;
int len,id,pos;
Node() {}
Node(int _len) { len=_len; memset(ch,0,sizeof ch); f=0; }
}sam[N],*root,*last;
int tot; ///SAM_size
Node* newnode(int len)
{
sam[tot]=Node(len);
sam[tot].id=tot;
return &sam[tot++];
}
Node* newnode(Node* p)
{
sam[tot]=*p;
sam[tot].id=tot;
return &sam[tot++];
}
void SAM_init()
{
tot=0;
root=last=newnode(0);
sam[0].pos=0;
}
#define node Node
void add(int x,int len)
{
Node *p=last,*np=newnode(p->len+1);
np->pos=len; last=np;
while(p&&!p->ch[x]) p->ch[x]=np,p=p->f;
if(!p) { np->f=root;return; }
node *q=p->ch[x];
if(q->len==p->len+1) { np->f=q; return; } ///!!!
node* nq=newnode(q);
nq->len=p->len+1;
q->f=nq; np->f=nq;
for(;p&&p->ch[x]==q;p=p->f) p->ch[x]=nq;
}
void SAM_build(char s[])
{
SAM_init();
for(int i=0;s[i];i++) add(s[i]-'a',i+1);
}
Node* top[N]; ///toposort
char s[N];
int c[N];
int dp[N];
void Max(int& a,int b) { if(a<b) a=b; }
int main()
{
int re; cin>>re; int ca=1;
while(re--)
{
int m; cin>>m;
scanf("%s",s);
SAM_build(s);
memset(c,0,sizeof c);
memset(dp,0,sizeof dp);
memset(top,0,sizeof top);
for(int i=0;i<tot;i++) c[sam[i].len]++;
for(int i=1;i<=tot;i++) c[i]+=c[i-1];
for(int i=0;i<tot;i++)
top[--c[sam[i].len]]=&sam[i];
while(m--)
{
node* p=root;
scanf("%s",s);
int len=strlen(s);
int tmp=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(p->ch[x])
{
tmp++;
p=p->ch[x];
Max(dp[p->id],tmp);
}
else {
while(p&&!p->ch[x])p=p->f;
if(p) {
tmp=p->len+1;
p=p->ch[x];
Max(dp[p->id],tmp);
}
else { tmp=0; p=root; }
}
}
}
ll ans=0;
for(int i=tot-1;i>0;i--)
{
Node *p=top[i];
if(dp[p->id]==0)
{
ans+=p->len-p->f->len;
continue;
}
if(p->f) Max(dp[p->f->id],dp[p->id]);
if(dp[p->id]<p->len) ans+=p->len-dp[p->id];
}
printf("Case %d: %I64d
",ca++,ans);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.