fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define maxn 105
  5. #define base 7243
  6.  
  7.  
  8. char s[1005];
  9. int h[1005];
  10. int pb[1005];
  11.  
  12. char ss[maxn][maxn];
  13. int hh[maxn];
  14.  
  15. int len;
  16. int L[maxn];
  17. int n;
  18.  
  19. bool used[maxn];
  20.  
  21. bool goal=false;
  22.  
  23. int iter[maxn];
  24. int in=0;
  25.  
  26. void Try(int index){
  27. 	if(index==len){
  28. 		goal=true;
  29. 		cout<<in<<endl;
  30. 		for(int i=0;i<in;++i){
  31. 			cout<<ss[iter[i]]<<endl;
  32. 		}
  33. 	}
  34. 	if(index>len or goal){
  35. 		return;
  36. 	}
  37. 	for(int i=0;i<n;++i){
  38. 		if(used[i]) continue;
  39. 		if(hh[i]==h[index+L[i]]-h[index]*pb[L[i]]){
  40. 			used[i]=true;
  41. 			iter[in++]=i;
  42. 			Try(index+L[i]);
  43. 			--in;
  44. 			used[i]=false;
  45. 		}
  46. 	}
  47. }
  48.  
  49.  
  50. int main() {
  51. 	cin>>s;
  52. 	cin>>n;
  53. 	for(int i=0;i<n;++i){
  54. 		cin>>ss[i];
  55. 	}
  56.  
  57. 	len=strlen(s);
  58. 	pb[0]=1;
  59. 	h[0]=0;
  60. 	for(int i=1;i<=len;++i){
  61. 		pb[i]=pb[i-1]*base;
  62. 		h[i]=h[i-1]*base+s[i-1];
  63. 	}
  64.  
  65. 	for(int i=0;i<n;++i){
  66. 		int j;
  67. 		int x=strlen(ss[i]);
  68. 		L[i]=x;
  69. 		int t=0;
  70. 		for(j=0;j<x;++j){
  71. 			//cout<<t<<" ";
  72. 			t=t*base+ss[i][j];
  73. 		}
  74. 		//cout<<endl;
  75. 		hh[i]=t;
  76. 	}
  77.  
  78. 	//cout<<hh[0]<<" "<<ss[0]<< endl;
  79. 	//cout<<h[5]-h[2]*pb[3]<<" " <<pb[3]<<endl;
  80.  
  81. 	fill(used,used+n,false);
  82. 	Try(0);
  83.  
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
KythiHocsinhGioi
5
thi
Ky
Gioi
Ythi
Hocsinh
stdout
copy 
4
Ky
thi
Hocsinh
Gioi
https://ideone.com/vdOBMK
ghep chuoi
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!