首页 > 试题广场 >

HDU 2203 亲和串

[编程题]HDU 2203 亲和串

热度指数：121 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

人随着岁数的增长是越大越聪明还是越大越笨，这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考，因为他在很小的时候就知道亲和串如何判断了，但是发现，现在长大了却不知道怎么去判断亲和串了，于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。
亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。

输入描述:

本题有多组测试数据，每组数据的第一行包含输入字符串s1,第二行包含输入字符串s2，s1与s2的长度均小于100000。

输出描述:

如果s2是s1的亲和串，则输出"yes"，反之，输出"no"。每组测试的输出占一行。

示例1

输入

AABCD
CDAA
ASD
ASDF

输出

yes
no

算法知识视频讲解

推荐

书名待定

#include<stdio.h>
#include<string.h>
int main()
{
    char s1[200001],s2[110000];
    while(~scanf("%s %s",s1,s2))
    {
        sprintf(s1,"%s%s",s1,s1);
        if(strstr(s1,s2))puts("yes");
        else puts("no");
    }
}

发表于 2015-10-28 15:18:01 回复(0)

Black＆Blue

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s1 = sc.next();
String s2 = sc.next();
// 将s1字符串拼接, 然后判断是否包含s2
if(s1.length() >= s2.length() && (s1+s1).contains(s2)) {
System.out.println("yes");
} else {
System.out.println("no");
}
}
}
}

可以用kmp来判断s1+s1是否包含s2

发表于 2018-02-26 12:12:30 回复(0)

offer去哪里了

import java.util.Scanner;

/**
 * https://www.nowcoder.com/questionTerminal/ca68cb11b1a94ddeb3181274d4e94760
 */
public class Main {

    public static int[] getNextArr(char[] ch){
        if (ch.length == 1){
            return new int[] { -1 };
        }
        int[] next = new int[ch.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        for (int i = 2; i < ch.length; i++) {
            if (ch[i-1] == ch[cn]){
                next[i] = ++cn;
            }else if (cn > 0){
                cn = next[cn];
            }else {
                next[i] = 0;
            }
        }
        return next;
    }

    public static int judge(char[] ch1, char[] ch2, int[] next){
        int l1 = 0;
        int l2 = 0;
        while(l1 < ch1.length && l2 < ch2.length){
            if (ch1[l1] == ch2[l2]){
                l1++;
                l2++;
            }else if(next[l2] == -1){
                l1++;
            }else {
                l2 = next[l2];
            }
        }
        return l2 == ch2.length ? l1 - l2 : -1;
    }
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       while (sc.hasNext()) {
            String str1 = sc.next();
            String str2 = sc.next();
            str1 = str1 + str1;
            if (str1.length() < str2.length()) {
                System.out.println("no");
            } else {
                char[] ch1 = str1.toCharArray();
                char[] ch2 = str2.toCharArray();
                int[] next = getNextArr(ch2);
                int res = judge(ch1, ch2, next);
                if (res != -1) {
                    System.out.println("yes");
                } else {
                    System.out.println("no");
                }
            }
        }

    }

}

KMP实现

编辑于 2018-09-09 17:23:37 回复(0)

dijkstra11

#include <string>
#include <iostream>
using namespace std;

void computePrefix(int *next, int m, string patt)
{
   int q = -1, k = 1;
   next[0] = -1;
   while(k < m){
       while(q > -1 && patt[q + 1] != patt[k])
           q = next[q];
       if(patt[q + 1] == patt[k])
           ++q;
       next[k++] = q;
   }
}

bool kmp(string str, string patt)
{
   int n = str.size();
   int m = patt.size();
   int *next = new int[m];
   computePrefix(next, m, patt);
   int q = -1;
   for(int i = 0; i != n; ++i){
       while(q > -1 && patt[q + 1] != str[i])
           q = next[q];
       if(patt[q + 1] == str[i])
           ++q;
       if(q + 1 == m)
           return true;
   }
   return false;
}

int main(int argc, char const *argv[])
{
   string str1, str2;
   while(cin >> str1 >> str2){
       str1 = str1 + str1;
       if(kmp(str1, str2))
           cout << "yes" << endl;
       else
           cout << "no" << endl;
   }
   return 0;
}

发表于 2018-04-15 20:31:21 回复(0)