HDU 2896 바이러스 침입 & & HDU 3065 바이러스 침입 지속 중
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10518 Accepted Submission(s): 2730
Problem Description
태양의 빛 이 점점 달 에 가 려 지면 세상 은 빛 을 잃 고 대 지 는 가장 어두 운 순간 을 맞이 합 니 다...이런 순간 에 사람들 은 매우 흥분 합 니 다. 우 리 는 살 아 있 는 동안 500 년 에 한 번 있 는 세계관 을 볼 수 있 습 니 다. 그것 이 얼마나 행복 한 일 입 니까?
그러나 인터넷 에는 항상 그런 사이트 들 이 있 는데 민중 의 호기심 을 빌려 일식 을 소개 한 다 는 명목 으로 바 이러 스 를 마구 퍼 뜨리 기 시작 했다.작은 t 는 불행 하 게 도 피해자 중의 하나 가 되 었 다.작은 t 가 이렇게 화가 나 서 그 는 세계 의 모든 바 이러 스 를 가 진 사 이 트 를 찾아내 기로 결정 했다.물론 불가능 하 다 는 것 은 누구나 다 안다.작은 t 는 이 할 수 없 는 임 무 를 완수 하 겠 다 고 고집 했다. 그 는 "자손 이 끝 이 없어!"라 고 말 했다.
모든 일 은 시작 이 어렵다. 작은 t 는 많은 바이러스 의 특징 코드 를 수집 하고 기괴 한 사이트 의 소스 코드 를 수집 했다. 그 는 이런 사이트 에서 어떤 바이러스 가 있 는 지, 또 어떤 바 이러 스 를 가지 고 있 는 지 알 고 싶 어 한다.그 가 도대체 바 이러 스 를 가 진 사 이 트 를 얼마나 수 집 했 는 지 궁금 하 다.이때 그 는 어떻게 손 을 써 야 할 지 몰 랐 다.그래서 여러분 께 도움 을 청 하고 싶 습 니 다.작은 t 는 또 성질 이 급 하 니까 빨리 해결 할 수록 좋아요.
Input
첫 번 째 줄 은 하나의 정수 N (1 < = N < = 500) 으로 바이러스 특징 코드 의 개 수 를 나타 낸다.
다음 N 줄 은 줄 마다 바이러스 특징 코드 를 표시 하고 특징 코드 문자열 의 길 이 는 20 - 200 사이 입 니 다.
모든 바 이러 스 는 하나의 번호 가 있 는데, 이에 따라 1 - N 이다.
서로 다른 번호 의 바이러스 특징 코드 는 같 지 않 을 것 이다.
그 다음 줄 에 하나의 정수 M (1 & lt; = M & gt; = 1000) 이 있어 사이트 수 를 나타 낸다.
다음 M 줄 은 줄 마다 하나의 사이트 소스 코드 를 표시 하고 소스 문자열 의 길 이 는 7000 - 10000 사이 입 니 다.
사이트 마다 하나의 번호 가 있 는데 이에 따라 1 - M 이다.
이상 문자열 의 문 자 는 모두 ASCII 코드 에서 볼 수 있 는 문자 입 니 다 (리 턴 은 포함 되 지 않 습 니 다).
Output
순서대로 다음 과 같은 형식 으로 출력 하고 사이트 번호 에 따라 어 릴 때 부터 큰 수출 을 하 며 바 이러 스 를 가 진 사이트 번호 와 바이러스 번 호 를 포함 하 며 줄 마다 독 을 함유 한 사이트 정 보 를 포함한다.
웹 사이트 번호: 바이러스 번호, 바이러스 번호...
사칭 후 빈 칸 이 하나 있 는데 바이러스 번 호 는 작은 것 부터 큰 것 까지 배열 되 고 두 바이러스 번호 사 이 는 하나의 빈 칸 으로 분리 되 며 한 사이트 에 바이러스 가 포함 되면 바이러스 수 는 3 개 를 넘 지 않 는 다.
마지막 줄 출력 통계 정 보 는 다음 과 같 습 니 다.
바이러스 사이트 수
사칭 후 빈 칸 이 하나 있다.
Sample Input
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc
Sample Output
web 1: 1 2 3
total: 1
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
#define prt(k) cout<<#k"="<<k<<endl;
#define ll long long
const int NODE=100200;
const int CHAR=128;
int ch[NODE][133];
int val[NODE];
int last[NODE];
int sz;
int f[NODE];
int cnt[NODE];
void init()
{
sz=1;
memset(ch[0],0,sizeof ch[0]);
}
void insert(char *s,int v)
{
int len=strlen(s), u=0;
for(int i=0;i<len;i++)
{
int c=s[i];
if(ch[u][c]==0)
{
memset(ch[sz],0,sizeof ch[sz]);
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=v;
}
vector<int> ans;
void gao(int j)
{
if(j==0) return;
cnt[val[j]]++; // prt(val[j]);
gao(last[j]);
}
int find(char* T)
{
int len=strlen(T);
int j=0;
for(int i=0;i<len;i++)
{
j=ch[j][T[i]];
if(val[j]) gao(j);
else if(last[j]) gao(last[j]);
}
}
int build()
{
queue<int>q ;
f[0]=0;
for(int c=0;c<CHAR;c++)
{
int u=ch[0][c];
if(u) { f[u]=0; q.push(u); last[u]=0; }
}
while(!q.empty())
{
int r=q.front();q.pop();
for(int c=0;c<CHAR;c++)
{
int u=ch[r][c];
if(!u) { ch[r][c]=ch[f[r]][c]; continue; }
q.push(u);
int v=f[r];
while(v && !ch[v][c]) v=f[v];
f[u]=ch[v][c];
last[u] = val[f[u]] ? f[u] : last[f[u]];
}
}
}
int n,m;
char buf[10022];
int main()
{
while(scanf("%d",&n)==1&&n)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",buf);
insert(buf,i);
}
build();
scanf("%d",&m);
int tot=0;
for(int i=1;i<=m;i++)
{
scanf("%s",buf);
memset(cnt,0,sizeof cnt);
find(buf);
vector<int> ans;
for(int i=1;i<=n;i++)
if(cnt[i])
ans.push_back(i);
int t=ans.size();
if(t>0)
{
tot++;
printf("web %d:",i);
for(int i=0;i<t;i++)
{
printf(" %d",ans[i]);
}
putchar(10);
}
}
printf("total: %d
",tot);
}
}바이러스 침투 지속 중
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5927 Accepted Submission(s): 2113
Problem Description
작은 t. 여러분 이 그의 지난 문 제 를 해결 해 주 셔 서 감사합니다.하지만 바이러스 의 습격 은 계속 되 고 있다.작은 t 의 끊 임 없 는 노력 으로 그 는 인터넷 에서 '모든 악의 근원' 을 발견 했다.이것 은 방대 한 바이러스 사이트 이다. 그 는 많은 바 이러 스 를 가지 고 있 지만 이 사이트 에 포 함 된 바 이러 스 는 매우 이상 하 다. 이런 바이러스 의 특징 코드 는 매우 짧 고 '영어 대문자' 만 포함한다.물론 작은 t 는 백성 을 위해 해 를 제거 하고 싶 지만 작은 t 는 준비 되 지 않 은 전쟁 을 하지 않 는 다.지피지기, 백전백승, 작은 t 가 먼저 해 야 할 일 은 이 바이러스 사이트 의 특징 을 아 는 것 이다. 얼마나 다른 바 이러 스 를 포함 하고 있 는 지, 모든 바이러스 가 몇 번 나 타 났 는 지.여러분 이 그 를 좀 더 도와 줄 수 있 습 니까?
Input
첫 번 째 줄 은 하나의 정수 N (1 < = N < = 1000) 으로 바이러스 특징 코드 의 개 수 를 나타 낸다.
다음 N 줄 은 줄 마다 바이러스 특징 코드 를 표시 하고 특징 코드 문자열 의 길 이 는 1 - 50 사이 이 며 '영문 대문자' 만 포함 합 니 다.임의의 두 바이러스 특징 코드 는 완전히 같 지 않 을 것 이다.
그 다음 줄 에 서 는 '모든 악의 근원' 사이트 의 원본 코드 를 표시 하고 원본 문자열 의 길 이 는 20000 이내 이다.문자열 의 문 자 는 모두 ASCII 코드 에서 볼 수 있 는 문자 입 니 다 (리 턴 은 포함 되 지 않 습 니 다).
Output
다음 형식 으로 줄 마다 바이러스 발생 횟수 를 출력 합 니 다.나타 나 지 않 은 바 이러 스 는 출력 할 필요 가 없다.
바이러스 특징 코드: 출현 횟수
콜론 후 빈 칸 이 있 으 며, 바이러스 특징 코드 의 입력 순서에 따라 출력 합 니 다.
Sample Input
3
AA
BB
CC
ooxxCC%dAAAoen....END
Sample Output
AA: 2
CC: 1
Hint
Hit： 。 。 Sample 。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
#define prt(k) cout<<#k"="<<k<<endl;
#define ll long long
const int NODE=100200;
const int CHAR=128;
int ch[NODE][133];
int val[NODE];
int last[NODE];
int sz;
int f[NODE];
int cnt[NODE];
void init()
{
sz=1;
memset(ch[0],0,sizeof ch[0]);
}
void insert(char *s,int v)
{
int len=strlen(s), u=0;
for(int i=0;i<len;i++)
{
int c=s[i];
if(ch[u][c]==0)
{
memset(ch[sz],0,sizeof ch[sz]);
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=v;
}
vector<int> ans;
void gao(int j)
{
if(j==0) return;
cnt[val[j]]++; // prt(val[j]);
gao(last[j]);
}
int find(char* T)
{
int len=strlen(T);
int j=0;
for(int i=0;i<len;i++)
{
j=ch[j][T[i]];
if(val[j]) gao(j);
else if(last[j]) gao(last[j]);
}
}
int build()
{
queue<int>q ;
f[0]=0;
for(int c=0;c<CHAR;c++)
{
int u=ch[0][c];
if(u) { f[u]=0; q.push(u); last[u]=0; }
}
while(!q.empty())
{
int r=q.front();q.pop();
for(int c=0;c<CHAR;c++)
{
int u=ch[r][c];
if(!u) { ch[r][c]=ch[f[r]][c]; continue; }
q.push(u);
int v=f[r];
while(v && !ch[v][c]) v=f[v];
f[u]=ch[v][c];
last[u] = val[f[u]] ? f[u] : last[f[u]];
}
}
}
int n,m;
char buf[2002002];
char dic[1111][444];
int main()
{
while(scanf("%d",&n)==1&&n)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",dic[i]);
insert(dic[i],i);
}
build();
int tot=0;
scanf("%s",buf);
memset(cnt,0,sizeof cnt);
find(buf);
for(int i=1;i<=n;i++)
if(cnt[i])
printf("%s: %d
",dic[i],cnt[i]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JAVA- 소스 코드 분할(Package 사용)▪️test45.java 소스 코드 ▪️test47.java 소스 코드 ▪️실행 결과 더하면 12, 당기면 8 ▪️예① 클래스 이름에 대한 완전한 입력 생략 import 문 사용 ▪️예① test45.java 소스 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
