hdu1238

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

15 9月 2015

Substrings

Problem Description

You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.

Output

There should be one line per test case containing the length of the largest string found.

Sample Input

ABCD

BCDFF

BRCD

rose

orchid

Sample Output

Author

Asia 2002, Tehran (Iran), Preliminary

题目类型：字符串处理

算法分析：首先找到给出的字符串组中长度最小的那一个，然后从大到小枚举该字符串的所有子串，对于每个子串，判断它和它的反转串是否在其他的字符串中存在，如果都存在一种情况(正串或者是反串)，则退出判断，输出结果

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 136 + 66;
const double EPS = 1e-10;

string s[maxn];

int main()
{
//    ifstream cin ("aaa.txt");

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;
        int i, minval = INF, index = 0;
        for (i = 0; i < n; i++)
        {
            cin >> s[i];

            int len = s[i].size ();

            if (minval > len)
            {
                minval = len;
                index = i;
            }
        }

        string temp_a, temp_b;
        int j;
        bool is_find = false;

        for (i = minval; i >= 1; i--)
        {
            for (j = 0; j + i <= minval; j++)
            {
                temp_a = s[index].substr (j, i);

                temp_b = temp_a;
                reverse (temp_b.begin (), temp_b.end ());

                int k;
                for (k = 0; k < n; k++)
                    if (string :: npos == s[k].find (temp_a) && string :: npos == s[k].find (temp_b))
                        break;

                if (k == n)
                {
                    is_find = true;
                    break;
                }
            }

            if (is_find)
                break;
        }

        cout << i << endl;

    }

return 0;
}

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 136 + 66;

const double EPS = 1e-10;

string s[maxn];

int main()

{

// ifstream cin ("aaa.txt");

int t;

cin >> t;

while (t--)

{

int n;

cin >> n;

int i, minval = INF, index = 0;

for (i = 0; i < n; i++)

{

cin >> s[i];

int len = s[i].size ();

if (minval > len)

{

minval = len;

index = i;

}

string temp_a, temp_b;

int j;

bool is_find = false;

for (i = minval; i >= 1; i--)

{

for (j = 0; j + i <= minval; j++)

{

temp_a = s[index].substr (j, i);

temp_b = temp_a;

reverse (temp_b.begin (), temp_b.end ());

int k;

for (k = 0; k < n; k++)

if (string :: npos == s[k].find (temp_a) && string :: npos == s[k].find (temp_b))

break;

if (k == n)

{

is_find = true;

break;

}

if (is_find)

break;

}

cout << i << endl;

}

return 0;

}

hdu1232

hdu1240

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

hdu1238

Substrings

分类目录

标签云

书签

近期评论