java--二进制字符串匹配的问题
2013-06-17 14:57:35      个评论

Given two strings A and B, whose alphabet consist only ‘0’ and ‘1’. Your task is only to tell how many times does A appear as a substring of B? For example, the text string B is ‘1001110110’ while the pattern string A is ‘11’, you should output 3, because the pattern A appeared at the posit

The first line consist only one integer N, indicates N cases follows. In each case, there are two lines, the first line gives the string A, length (A) <= 10, and the second line gives the string B, length (B) <= 1000. And it is guaranteed that B is always longer than A.

For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.

3
11
1001110110
101
110010010010001
1010
110100010101011 样例输出

3
0
3

[java]
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();//n=3

String str;
String pattern;
//循环3次
while(n > 0){
pattern = sc.next();//11
str = sc.next();//1001110110

int index = 0;//记录pattern在str中出现的索引
int count = 0;//记录出现的次数，默认=0

while(index != -1){
index = str.indexOf(pattern);//index = 3
if(index != -1){
//说明存在pattern
count ++ ;//count = 1
str = str.substring(index+1);//此时str = 110110
}
}

System.out.println(count);

n--;
}
}

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();//n=3

String str;
String pattern;
//循环3次
while(n > 0){
pattern = sc.next();//11
str = sc.next();//1001110110

int index = 0;//记录pattern在str中出现的索引
int count = 0;//记录出现的次数，默认=0

while(index != -1){
index = str.indexOf(pattern);//index = 3
if(index != -1){
//说明存在pattern
count ++ ;//count = 1
str = str.substring(index+1);//此时str = 110110
}
}

System.out.println(count);

n--;
}
}
}