hdoj

Number Sequence  ------------------------hdoj  1711
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 57190    Accepted Submission(s): 22846


Problem Description
Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.
 

Input
The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].
 

Output
For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
 

Sample Input
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1
 

Sample Output
6
-1

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const int maxn = 1000000;
const int maxm=10000;
int text[maxn];
int pattern[maxm]; 
int nextTable[maxn];

void getNextTable(int m){
	
	int j=0;
	nextTable[j] = -1;
	int t = nextTable[j];
	while(j <m){
		if(t == -1 || pattern[t] == pattern[j]){
			++t;++j;
			nextTable[j] = t;
		}else{
			t = nextTable[t];
		}
	}
	return ;
} 
int KMP(int n,int m){
	getNextTable(m);
	
	int i=0;//主串 
	int j=0;//匹配的串 
	while(i<n && j<m){
		if(j==-1 || text[i] == pattern[j]){
			++i;++j;
		}else{
			j=nextTable[j];
		}
	}
	if(j == m){
		return i-j+1;
	}else{
		return -1;
	}
}
int main(){
	int casenum;
	scanf("%d",&casenum);
	while(casenum--){
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i=0;i<n;i++){
			scanf("%d",&text[i]);
		}
		for(int i=0;i<m;i++){
			scanf("%d",&pattern[i]);
		}
		int pos = KMP(n,m);
		printf("%d\n",pos);
	}
	
	return 0;
} 


poj  3461
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const int maxn = 10010;
int nextTable[maxn];

void getNextTable(string pattern){
	int m= pattern.size();
	int j=0;
	nextTable[j] = -1;
	int t = nextTable[j];
	while(j <m){
		if(t == -1 || pattern[t] == pattern[j]){
			++t;++j;
			nextTable[j] = t;
		}else{
			t = nextTable[t];
		}
	}
	return ;
} 
int KMP(string text,string pattern){
	getNextTable(pattern);
	int n=text.size();
	int m=pattern.size();
	int i=0;//主串 
	int j=0;//匹配的串 
	int num=0;
	while(i<n){
		if(j==-1 || text[i] == pattern[j]){
			++i;++j;
		}else{
			j=nextTable[j];
		}
	}
	if(j == m){
		num++;
		j=nextTable[j]; //允许字符重复匹配 
		//j=0;	//不允许重复匹配 
	}
	return num;
}
int main(){
	int casenum;
	scanf("%d",&casenum);
	while(casenum--){
		string text,pattern;
		cin>>pattern>>text;
		int pos = KMP(text,pattern);
		printf("%d\n",pos);
	}
	
	return 0;
} 




/*
线性数据结构 向量 栈 队列 
vector<int> vector; 类似于动态数组 (int*)molloc(sizeof(int)) 
int a[]={1,2,3,4}; 
队列 queue
栈 stack 

#include<cstdio>
#include<iostream>
#include<queue> 
using namespace std; 
struct Animal{
	int num;
	int order;
	Animal(){}
	Animal(int n,int o):num(n),order(o){}
}; 
queue<Animal> cats;
queue<Animal> dogs;
int main(){
	int n;
	scanf("%d",&n);
	int order=0;
	for(int i=0;i<n;i++){
		int method,type;
		scanf("%d %d",&method,&type);
		if(method == 1){
			if(type > 0){
				dogs.push(Animal(type,order++));
			}else{
				cats.push(Animal(type,order++));
			}
		}else{
			if(type == 0 && !dogs.empty() && !cats.empty()){
				if(dogs.front().order < cats.front().order){
					printf("%d ",dogs.front().num);
					dogs.pop();
				}else{
					printf("%d ",cats.front().num);
					cats.pop();
				}
			}else if(type == 0 && dogs.empty() && !cats.empty()){
				printf("%d ",cats.front().num);
				cats.pop();
			}else if(type == 0 && !dogs.empty() && cats.empty()){
				printf("%d ",dogs.front().num);
				dogs.pop();
			}else if(type == 1 && !dogs.empty()){
				printf("%d ",dogs.front().num);
				dogs.pop();
			}else if(type == -1 && !cats.empty()){
				printf("%d ",cats.front().num);
				cats.pop();
			}
		}
	} 
	printf("\n"); 
	return 0;
}


//括号匹配

#include<cstdio>
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(){
	string str;
	while(cin >>str){
		stack<int> stacks;
		string ans(str.size(), ' ');
		for(int i=0; i<str.size(); i++){
			if(str[i] == '('){
				stacks.push(i);
			}else if(str[i] ==')'){
				if(!stacks.empty()){
					stacks.pop();
				}else{
					ans[i]='?';
				}
			}
		}
		while(!stacks.empty()){
			ans[stacks.top()]='$';
			stacks.pop();
		}
		cout << str <<endl;
		cout << ans <<endl;
	} 
	
	return 0;
} 

*/
// 表达式求值

#include<cstdio>
#include<iostream>
#include<cctype>
#include<string>
#include<stack>
using namespace std;
int Priority(char c){
	if(c =='#'){
		return 0;
	}else if( c=='$'){
		return 1;
	}else if(c=='+' || c=='-'){
		return 2;
	}else if(c =='*' || c=='/'){
		return 3;
	}
} 
double Getnum(string str,int& index){
	double num =0;
	while(isdigit(str[index])){
		num = num*10 +str[index]-'0';
		index++;
	}
	return num;
}
double Calculate(double x, double y,char op){
	double res = 0;
	if(op =='+'){
		res = x+y;
	}else if(op == '-'){
		res = x-y;
	}else if(op =='*'){
		res = x*y;
	}else if(op =='/'){
		res = x/y;
	}
	return res;
}
int main(){
	stack<char>oper;
	stack<double> data;
	string str;
	getline(cin, str);
	int index=0;
	oper.push('#');
	str +='$';
	while(index <str.size()){
		if(str[index] ==' '){
			index++;
		}else if(isdigit(str[index])){
			data.push(Getnum(str,index));
		}else{
			if(Priority(oper.top()) < Priority(str[index])){
				oper.push(str[index]);
				index++;
			}else{
				double y = data.top();
				data.pop();
				double x = data.top();
				data.pop();
				data.push(Calculate(x,y,oper.top()));
				oper.pop();
			} 
		}
	} 
	printf("%.2f\n",data.top());
	return 0;
}