游客 注册 | 登录
中文 | En

1041 - 字符串匹配1

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

给你一个字符串A和一个字符串B，请你计算字符串B的所有旋转形式在字符串A中的出现总次数。
说明：
如果将字符串B描述成B1B2...Bm的形式（m是B的长度），那么B1B2...Bm-1Bm，B2B3...BmB1，...，BmB1...Bm-2Bm-1就是字符串B的所有旋转形式。

题目输入

输入包含多组测试数据。每组输入为两行，第一行输入字符串A，第二行输入字符串B。A的长度不超过1000，B的长度不超过100，所有字符串仅包含小写字母。

题目输出

对于每组输入，输出字符串B的所有旋转形式在字符串A中的出现总次数。

输入/输出样例

输入格式

abab
ab
aaaa
a
aaaa
aa

输出格式

3
4
3

C语言解答

#include<stdio.h>
#include<string.h>
void sort_string(char a[])
{
	int i,j,len=strlen(a);
	char t;
	for(i=0;i<len;i++)
	{
		for(j=i+1;j<len;j++)
		{
			if(a[i]>a[j])
			{
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
	}
}
int main()
{
	char mstr[1001],sstr[101],temp[101];
	while(scanf("%s",mstr)!=EOF)
	{
		scanf("%s",sstr);
		int i,endpos,mlen=strlen(mstr),slen=strlen(sstr);
		int count=0;
		sort_string(sstr);
		//printf("@@%s\n",sstr);
		for(i=0;i<=mlen-slen;i++)
		{
			endpos=i+slen;
			char t=mstr[endpos];
			mstr[endpos]='\0';
			strcpy(temp,&mstr[i]);
			mstr[endpos]=t;
			sort_string(temp);
			//printf("!!%s\n",temp);
			if(strcmp(temp,sstr)==0)
				count++;
		}
		printf("%d\n",count);
	}
	return 0;
}

C++解答

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

int main()
{
	char a[1001],b[101];
	string A,B,C,D;
	int i,j,la,lb,s;
	while(scanf("%s%s",a,b)!=EOF)
	{
		A=a;
		B=b;
		la=A.length();
		lb=B.length();
		for(s=i=0;i<la;i++)
		{
			C=A.substr(i,lb);
			for(j=0;j<lb;j++)
			{
				D=B.substr(j);
				D.append(B,0,j);
				if(C==D)
				{
					s++;
					break;
				}
			}
		}
		printf("%d\n",s);
	}
	return 0;
}

Java解答

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{

    public static void main(String[] args) throws IOException
    {
	// TODO Auto-generated method stub

	String A, B;
	int lenA, lenB, len, count,count2, duplicate;
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	A = br.readLine();
	B = br.readLine();
	while(true)
	{
	    
	    if (A == null || B == null)
	    {
		break;
	    }
	    lenA = A.length();
	    lenB = B.length();
	    
	    count = 0;
	    len = lenA - lenB + 1;
	    for(int i = 0;i < len;i++)
	    {
		count2=0;
		for(int j = 0;j < lenB;j++)
		{

		    if (equalsAB(A, i, B, j, lenB))
		    {
			duplicate = 0;
			count2++;
			for(int k = j + 1;k < lenB;k++)
			{
			    if (equalsBB(B, j, B, k, lenB))
			    {
				duplicate=1;// 重复的
				break;
			    }
			}
			count2 -= duplicate ;// 减去重复的
		    }
		}
		count+=count2;

	    }
	    System.out.println(count);
	    A = br.readLine();
	    B = br.readLine();
	}
    }

    static boolean equalsAB(String cs1, int offset1, String cs2, int offset2, int len)
    {
	for (int i = 0; i < len; i++)
	{
		if (cs1.charAt(offset1+i)!=cs2.charAt((offset2+i)%len))
		{
			return false;
		}
	}
	return true;
    }

    static boolean equalsBB(String cs1, int offset1, String cs2, int offset2, int len)
    {
	for(int i = 0;i < len;i++)
	{
	    if (cs1.charAt((offset1 + i) % len) != cs2.charAt((offset2 + i) % len))
	    {
		return false;
	    }
	}
	return true;
    }

}

Python解答

#b in a
def mycount(a,b):
    if a=='' or b=='':
        return 0
    count = 0
    j = 0
    while True:
        if b == a[j:(len(b)+j)]:
            count += 1
        j += 1
        if j + len(b)>len(a):break
    return count

while True:
    A = raw_input()
    B = raw_input()
    lst = []
    sumi = 0
    for i in range(0,len(B)):
        lst.append(B)
        B = B[1:len(B)] + B[0]
    lst2 = list(set(lst))
    #print lst2
    for i in lst2:
        sumi += mycount(A,i)
    print sumi
请先登陆