Hat’s Words (分成两个字符串考虑)

心已赠人 2021-12-03 23:23 162阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1247][http_acm.hdu.edu.cn_showproblem.php_pid_1247]

思路：

把字符串分成两个部分，看这两个部分是不是也在字典树上。如果在，就输出这个字符串。

这题我只想说静态内存真是容易爆！

1 #include <stdio.h>
     2 #include <string.h>
     3 #include <string>
     4 #include <iostream>
     5 #include <stdlib.h>
     6 #include <algorithm>
     7 
     8 using namespace std;
     9 const int MAX_NODE = 100000 + 10;
    10 const int CHARSET = 26;
    11 
    12 int trie[MAX_NODE][CHARSET]={
        0};
    13 int color[MAX_NODE]={
        0};
    14 int vis[MAX_NODE];
    15 char s[50001][300];
    16 int k = 1;
    17 
    18 void insert(char *w)
    19 {
    20     int len = strlen(w);
    21     int p = 0;
    22     for (int i=0;i<len;i++)
    23     {
    24         int c = w[i]-'a';
    25         if (!trie[p][c])
    26         {
    27             trie[p][c] = k;
    28             k++;
    29         }
    30         p = trie[p][c];
    31         vis[p]++;
    32     }
    33     color[p] = 1;
    34 }
    35 
    36 
    37 int search(char *s)
    38 {
    39     int len = strlen(s);
    40     int p = 0;
    41     for (int i=0;i<len;i++)
    42     {
    43         int c = s[i]-'a';
    44         if (!trie[p][c])
    45             return 0;
    46         p = trie[p][c];
    47     }
    48     return color[p] == 1;
    49 }
    50 
    51 
    52 int main()
    53 {
    54 #ifndef ONLINE_JUDGE
    55     freopen("../in.txt","r",stdin);
    56 #endif
    57     int t = 0;
    58     while (scanf("%s",s[t])!=EOF)
    59     {
    60         insert(s[t]);
    61         t++;
    62     }
    63     for (int i=0;i<t;i++)
    64     {
    65         for (int j=1;j<strlen(s[i]);j++)
    66         {
    67             char str1[1000]={
        '\0'};
    68             char str2[1000]={
        '\0'};
    69             strncpy(str1,s[i],j);
    70             strncpy(str2,s[i]+j,strlen(s[i])-j);
    71             if(search(str1) && search(str2))
    72             {
    73                 cout << s[i] << endl;
    74                 break;
    75             }
    76         }
    77     }
    78     return 0;
    79 }

转载于:https://www.cnblogs.com/-Ackerman/p/11209919.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1247]: http://acm.hdu.edu.cn/showproblem.php?pid=1247