100万文字の文字列Ｔにたいし1000文字までで構成される単語が10000個与えられるので、Ｔの部分文字列にどの単語が含まれているか高速に判定せよ。
計算は3秒以内に済ませること。
10000単語を（文字列、文字数）の順番でソートした文字列を表にする。
その表の中に経路をはわせればいい。
100万文字を1000文字ずつ1文字ずつずらしながら照合し、文字列は経路の中を通る。
経路の途中で単語の終わりまで来たらその単語は登場するとして照会する。
問題は経路の構築が難しいということ。
考えるのは好きだけど実装は苦手。
全単語を木にまとめる手法では速度はあったがメモリ使用量が超過した。
だから表の中に経路をはわせる手法で行きたい。
単語をソートした表を仮に以下とする。
aaaa
aab
aabb
bbbb
bbbc
bbbcd
cccc
という表にたいし
ｂｂｂｃｄe
がマッチするか探すには
一文字目がｂなのでｂが最初に出てくるのは4行目だから表の4行目にワープする。
ｂｂｂまでマッチする。
4行目の4列目でｂとｃに分岐するのでｃのある5行目の5列目にワープする
bbbcがマッチしたのでｂｂｂｃはマッチしたと記録する。
ｂｂｂｃの終わりに来たので下の行のｄにワープする。
ｂｂｂｃｄまでマッチして先がないので表の上の探索は終了する。
そんなイメージでマッチすれば高速にマッチする。
大事なのはワープ先がどこになるかの経路を事前に計算しておくと計算が速くなる。
最後に経路の末尾まで到達したら経路末尾を封鎖していくとすれば正答となりました。
一応８人しか正答者がいない問題の９人目の正答者になったが。
こんな問題が解けても、なんの意味もないし誰も評価してくれないし（ヒッキー人生で実質小学校卒だし）。
だから解いても欠片程も米粒の先っちょほども凄くないんだよな。
（私が大卒だったらＤＮＡとの高速マッチングとかそういう仕事につながるんだろうか？）
競技プログラムに対する世間からの評価はちょっとしたパズル。
これは正当な評価。
正答までの経過
１日目、木構造に纏めようとして失敗
２日目、木がダメなのでどう考えたらいいか思案
３日目 表に経路を開通すればいいと思いつくがin12で玉砕
４日目 正答、一度経路の末尾まで到達したらその末尾の経路を封鎖すればよいと思いつき自力で答えまで到達
#include<stdio.h>
#include<string>
#include<set>
#include<vector>
#include<iostream>
#include<map>
#include<list>
#include<string.h>
#include<algorithm>
#include<stack>
std::string T;
bool hit[10001];
std::list<char> ls;
int q;
std::set<int> sets;
struct E{
int no;
std::string str;
bool operator<(const E& e1)const{
for(unsigned int i=0;(i<str.size())&&(i<e1.str.size());i++){
if(str[i]!=e1.str[i])return str[i]<e1.str[i];
}
return str.size()<e1.str.size();
}
};
std::vector<E> qs;
std::map<int,std::map<char,int> > tree[10001];
int toNo[10001];
void print(){
std::map<int,std::map<char,int> >::iterator mmIt;
std::map<char,int>::iterator mIt;
printf(">>>>>>>>>>>data\n");
for(int i=0;i<q;i++){
printf("\n%s,%d",qs[i].str.c_str(),i);
for(mmIt=tree[i].begin();mmIt!=tree[i].end();mmIt++){
printf(",mm=%d ",(*mmIt).first);
for(mIt=(*mmIt).second.begin();mIt!=(*mmIt).second.end();mIt++){
printf("(%c %d)",(*mIt).first,(*mIt).second);
}
}
}
printf("\nlast\n");
}
void setNo(){
std::string str=qs[0].str;
int nowNo=qs[0].no;
for(int i=0;i<qs.size();i++){
if(qs[i].str==str){
toNo[qs[i].no]=nowNo;
}else{
str=qs[i].str;
nowNo=qs[i].no;
toNo[nowNo]=nowNo;
}
}
}
void hit_tree(){
//print2();
int y=0,x=0;
std::list<char>::iterator it;
std::map<int,std::map<char,int> >::iterator mmIt;
std::map<char,int>::iterator mIt;
it=ls.begin();
mmIt=tree[0].lower_bound(0);
if((mmIt==tree[0].end())||((*mmIt).second.empty()==true)){
return ;
}
int p=(*mmIt).first;
int oldY,oldX;
char oldC;
oldY=-1;
oldX=-1;
for(;it!=ls.end();){
for(;(x<p)&&(it!=ls.end());x++,it++){
if(qs[y].str[x]!=(*it))return;
}
if(x!=p)return;
if(tree[y][x].find((*it))==tree[y][x].end())return;
oldY=y;
oldX=p;
oldC=(*it);
y=tree[y][x][(*it)];
if(qs[y].str.size()==x+1){
//printf("(okb %s %d %d %d)\n",(qs[y].str.c_str()),y,x,p);
hit[toNo[qs[y].no]]=true;
}
if(it==ls.end())return ;
mmIt=tree[y].upper_bound(x);
if((mmIt==tree[y].end())||((*mmIt).second.empty()==true)){
tree[oldY][oldX].erase(oldC);
return ;
}
p=(*mmIt).first;
//printf("(%d %d %c %d)\n",y,x,(*it),p);
}
}
int main(){
std::cin>>T>>q;
memset(hit,false,sizeof(hit));
E e1;
for(int i=0;i<q;i++){
std::cin>>e1.str;
e1.no=i;
qs.push_back(e1);
}
std::sort(qs.begin(),qs.end());
bool ok=false;
//分岐点
for(int i=1;i<qs.size();i++){
if(qs[0].str!=qs[i].str){
ok=true;
break;
}
}
//ここを外すのを忘れずに
for(int i=0;i<qs.size();i++){
tree[i][qs[i].str.size()-1][qs[i].str[qs[i].str.size()-1]]=i;
}
setNo();
if(ok==true){
std::stack<E> st;
E e1;
E e2;
E e3;
std::string str1,str2,str3;
e1.str=qs[0].str;
e1.no=0;
st.push(e1);
int no3;
for(int i=1;i<q;i++)
{
//ここはたぶん完璧
str2=qs[i].str;
e2.str=str2;
e2.no=i;
e1=st.top();
str1=e1.str;
int p2=-1;
//printf("<s1=%s s2=%s>",str1.c_str(),str2.c_str());
if(str1==str2)continue;
for(int j=0;j<str1.size()&&j<str2.size();j++){
if(str1[j]!=str2[j]){
p2=j;
break;
}
}
if(p2==-1){
st.push(e2);
continue;
}
while(st.empty()==false){
E e1=st.top();
std::string str1=e1.str;
int p1=-1;
for(int j=0;(j<str1.size())&&(j<str2.size());j++){
if(str1[j]!=str2[j]){
p1=j;
break;
}
}
//printf("s1=%s s2=%s,%d %d ",str1.c_str(),str2.c_str(),p1,p2);
if(p1==-1){
break;
}
if(p1==p2){
e3.str=e1.str;
e3.no=e1.no;
}
if(p2!=p1)break;
st.pop();
}
if(e3.str!=""){
//printf("i=%d e3=%s\n\n",i,e3.str.c_str());
st.push(e3);
}
e1=st.top();
tree[e1.no][p2][e1.str[p2]]=e1.no;
tree[e1.no][p2][e2.str[p2]]=e2.no;
st.push(e2);
}
//難しい末尾の処理
std::map<int,int> pMemoR;
std::map<int,int>::iterator it;
pMemoR[qs[0].str.size()]=0;
for(int i=1;i<qs.size();i++){
std::string str2=qs[i].str;
std::string str1=qs[i-1].str;
if(str1==str2)continue;
it=pMemoR.upper_bound(str2.size());
pMemoR.erase(it,pMemoR.end());
int p2;
if(str1.size()==str2.size()){
for(int j=0;j<str2.size();j++){
if(str1[j]!=str2[j]){
p2=j;
break;
}
}
if(pMemoR.find(p2)!=pMemoR.end()){
int y=pMemoR[p2];
tree[y][p2][str2[p2]]=i;
}
}else if(str1.size()>str2.size()){
for(int j=0;j<str2.size();j++){
if(str1[j]!=str2[j]){
p2=j;
break;
}
}
if(pMemoR.find(p2)!=pMemoR.end()){
int y=pMemoR[p2];
tree[y][p2][str2[p2]]=i;
}
}else if(str1.size()<str2.size()){
p2=str1.size();
for(int j=0;j<str1.size();j++){
if(str1[j]!=str2[j]){
p2=j;
break;
}
}
if(pMemoR.find(p2)!=pMemoR.end()){
int y=pMemoR[p2];
tree[y][p2][str2[p2]]=i;
}
}
it=pMemoR.upper_bound(p2);
pMemoR.erase(it,pMemoR.end());
pMemoR[str2.size()]=i;
}
}
///print();
//return 0;
std::list<char>::iterator lIt;
for(int i=0;i<T.size();i++){
std::list<char>::iterator lIt=ls.begin();
if(i<1000){
ls.push_back(T[i]);
hit_tree();
}else{
ls.pop_front();
ls.push_back(T[i]);
hit_tree();
}
}
while(ls.empty()==false){
ls.pop_front();
hit_tree();
}
for(int i=0;i<q;i++){
if(hit[toNo[i]]==false){
printf("0\n");
}else{
printf("1\n");
}
}
}
最終更新：2016年01月06日 10:11
