hahaschool

POJ 1256 Anagram

January 17, 20152015-01-17hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>

using namespace std;


char chain[52] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
bool cmp(char a,char b){
    if (a == b) {
        return false;
    }
    bool flag = false;
    for (int i = 0;i < 52;i++) {
        if (a == chain[i]) {
            flag = true;
            break;
        }
        if (b == chain[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main(){
    int cnt;
    cin >> cnt;
    while (cnt--) {
        string toProc;
        cin >> toProc;
        while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

        }
        cout << toProc << endl;
        while (next_permutation(toProc.begin(), toProc.end(),cmp)) {
            cout << toProc << endl;
        }


    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

using namespace std;

char chain[52] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};

bool cmp(char a,char b){

if (a == b) {

return false;

}

bool flag = false;

for (int i = 0;i < 52;i++) {

if (a == chain[i]) {

flag = true;

break;

}

if (b == chain[i]) {

flag = false;

break;

}

return flag;

}

int main(){

int cnt;

cin >> cnt;

while (cnt--) {

string toProc;

cin >> toProc;

while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

}

cout << toProc << endl;

while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

cout << toProc << endl;

}

return 0;

}

next_permutation的返回bool值的含义是接下来还有没有可以用的排列。

然后要注意这个题的排序方式是特殊的，要自己构建排序函数。

排序函数返回值的意思是：如果返回true，则交换两个值，返回false，则不对两个值操作，所以如果a＝＝b一定要返回false，否则会死循环。

UVA 10420 List of Conquests

January 17, 20152015-01-17hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>

using namespace std;

int main(){
    int cnt;
    cin >> cnt;
    map<string, set<string> > container;
    while (cnt--) {
        string country;
        cin >> country;
        string name;
        getchar();
        getline(cin, name);
        container[country].insert(name);
    }
    map<string, set<string> >::iterator it;
    for (it = container.begin(); it != container.end(); it++) {
        cout << (*it).first << ' ' << (*it).second.size() << endl;
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

using namespace std;

int main(){

int cnt;

cin >> cnt;

map<string, set<string> > container;

while (cnt--) {

string country;

cin >> country;

string name;

getchar();

getline(cin, name);

container[country].insert(name);

}

map<string, set<string> >::iterator it;

for (it = container.begin(); it != container.end(); it++) {

cout << (*it).first << ' ' << (*it).second.size() << endl;

}

return 0;

}

STL的使用小练习

POJ 1002 487-3279

January 17, 20152015-01-17hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

int tel[10000000];

int main(){
    int cnt = 0;
    cin >> cnt;
    while (cnt--) {
        char toProc[1000];
        scanf(" %s",toProc);
        int len = strlen(toProc);
        int pow = 1000000,telnum = 0;
        for (int i = 0; i < len; i++) {
            if (isdigit(toProc[i])) {
                //digit
                telnum += pow * (toProc[i] - '0');
                pow /= 10;
            }else if (isalpha(toProc[i])) {
                //alpha
                if (toProc[i] == 'Q' || toProc[i] == 'Z' ) {
                    continue;
                }
                if (toProc[i] == 'A' || toProc[i] == 'B' || toProc[i] == 'C') {
                    telnum += pow * 2;
                }
                if (toProc[i] == 'D' || toProc[i] == 'E' || toProc[i] == 'F') {
                    telnum += pow * 3;
                }
                if (toProc[i] == 'G' || toProc[i] == 'H' || toProc[i] == 'I') {
                    telnum += pow * 4;
                }
                if (toProc[i] == 'J' || toProc[i] == 'K' || toProc[i] == 'L') {
                    telnum += pow * 5;
                }
                if (toProc[i] == 'M' || toProc[i] == 'N' || toProc[i] == 'O') {
                    telnum += pow * 6;
                }
                if (toProc[i] == 'P' || toProc[i] == 'R' || toProc[i] == 'S') {
                    telnum += pow * 7;
                }
                if (toProc[i] == 'T' || toProc[i] == 'U' || toProc[i] == 'V') {
                    telnum += pow * 8;
                }
                if (toProc[i] == 'W' || toProc[i] == 'X' || toProc[i] == 'Y') {
                    telnum += pow * 9;
                }
                pow /= 10;
            }
        }
        tel[telnum]++;
        //cout << telnum << endl;
    }
    bool flag = false;
    for (int i = 0; i < 10000000; i++) {
        if (tel[i] > 1) {
            flag = true;
            int pow = 1000000;
            int tmp = i;
            while (pow) {
                if (pow == 1000) {
                    cout << '-';
                }
                cout << tmp/pow;
                tmp -= (tmp/pow) * pow;
                pow /= 10;
            }
            cout << ' ' << tel[i] << endl;
        }
    }
    if (!flag) {
        cout << "No duplicates." << endl;
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int tel[10000000];

int main(){

int cnt = 0;

cin >> cnt;

while (cnt--) {

char toProc[1000];

scanf(" %s",toProc);

int len = strlen(toProc);

int pow = 1000000,telnum = 0;

for (int i = 0; i < len; i++) {

if (isdigit(toProc[i])) {

//digit

telnum += pow * (toProc[i] - '0');

pow /= 10;

}else if (isalpha(toProc[i])) {

//alpha

if (toProc[i] == 'Q' || toProc[i] == 'Z' ) {

continue;

}

if (toProc[i] == 'A' || toProc[i] == 'B' || toProc[i] == 'C') {

telnum += pow * 2;

}

if (toProc[i] == 'D' || toProc[i] == 'E' || toProc[i] == 'F') {

telnum += pow * 3;

}

if (toProc[i] == 'G' || toProc[i] == 'H' || toProc[i] == 'I') {

telnum += pow * 4;

}

if (toProc[i] == 'J' || toProc[i] == 'K' || toProc[i] == 'L') {

telnum += pow * 5;

}

if (toProc[i] == 'M' || toProc[i] == 'N' || toProc[i] == 'O') {

telnum += pow * 6;

}

if (toProc[i] == 'P' || toProc[i] == 'R' || toProc[i] == 'S') {

telnum += pow * 7;

}

if (toProc[i] == 'T' || toProc[i] == 'U' || toProc[i] == 'V') {

telnum += pow * 8;

}

if (toProc[i] == 'W' || toProc[i] == 'X' || toProc[i] == 'Y') {

telnum += pow * 9;

}

pow /= 10;

}

tel[telnum]++;

//cout << telnum << endl;

}

bool flag = false;

for (int i = 0; i < 10000000; i++) {

if (tel[i] > 1) {

flag = true;

int pow = 1000000;

int tmp = i;

while (pow) {

if (pow == 1000) {

cout << '-';

}

cout << tmp/pow;

tmp -= (tmp/pow) * pow;

pow /= 10;

}

cout << ' ' << tel[i] << endl;

}

if (!flag) {

cout << "No duplicates." << endl;

}

return 0;

}

真是良／心／题

首先要注意没有重复情形的时候，要输出一句话

然后以0开头的电话号码要处理

然后输入时候不能用cin

嗯就这样{(-_-)}

HDU 1264 Counting Squares

January 17, 20152015-01-17hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

#define MAXN 1000


bool board[MAXN][MAXN];


void outputBoard(){
    int res = 0;
    for (int x = 0; x < MAXN-1; x++) {
        for (int y = 0; y< MAXN;y++){
            if (board[y][x]) {
                res++;
            }
        }
    }
    cout << res << endl;
    memset(board, 0, sizeof(board));
}

int main(){
    memset(board, 0, sizeof(board));
    int startx = 0,starty = 0,endx = 0,endy = 0;
    while (cin >> startx >> starty >> endx >> endy){
        if (endx < startx) {
            swap(startx, endx);
        }
        if (endy < starty) {
            swap(starty, endy);
        }
        if (startx == -1 && starty == -1 && endx == -1 && endy == -1) {
            outputBoard();
            continue;
        }
        if (startx == -2 && starty == -2 && endx == -2 && endy == -2) {
            outputBoard();
            break;
        }
        for (int x = startx; x <= endx-1; x++) {
            for (int y = starty; y<= endy-1;y++){
                board[y][x] = true;
            }
        }


    }


}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

#define MAXN 1000

bool board[MAXN][MAXN];

void outputBoard(){

int res = 0;

for (int x = 0; x < MAXN-1; x++) {

for (int y = 0; y< MAXN;y++){

if (board[y][x]) {

res++;

}

cout << res << endl;

memset(board, 0, sizeof(board));

}

int main(){

memset(board, 0, sizeof(board));

int startx = 0,starty = 0,endx = 0,endy = 0;

while (cin >> startx >> starty >> endx >> endy){

if (endx < startx) {

swap(startx, endx);

}

if (endy < starty) {

swap(starty, endy);

}

if (startx == -1 && starty == -1 && endx == -1 && endy == -1) {

outputBoard();

continue;

}

if (startx == -2 && starty == -2 && endx == -2 && endy == -2) {

outputBoard();

break;

}

for (int x = startx; x <= endx-1; x++) {

for (int y = starty; y<= endy-1;y++){

board[y][x] = true;

}

两个对角线坐标的先后顺序不一定要自己判断，不好好看题谁也救不了。。。

HDU 1062 Text Reverse

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;




int main(int argc, char *argv[]) {
	int cnt;
	cin >> cnt;
	getchar();
	while (cnt--) {
		string str;
		getline(cin,str);
		str += ' ';
		string res;
		int startpos = 0,endpos = 0,status = 0;;
		for (int i = 0;i < str.size();i++) {
			if(str[i] == ' ' && status == 0){
				res += ' ';
			}
			else if (status == 0) {
				startpos = i;
				status++;
			}else if(status == 1 && str[i] == ' '){
				endpos = i-1;
				status--;
				for (int j = endpos;j >= startpos;j--) {
					res += str[j];
				}
				res += ' ';
			}else{

			}

		}
		res.erase(res.end()-1,res.end());
		cout << res << endl;
	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int main(int argc, char *argv[]) {

int cnt;

cin >> cnt;

getchar();

while (cnt--) {

string str;

getline(cin,str);

str += ' ';

string res;

int startpos = 0,endpos = 0,status = 0;;

for (int i = 0;i < str.size();i++) {

if(str[i] == ' ' && status == 0){

res += ' ';

}

else if (status == 0) {

startpos = i;

status++;

}else if(status == 1 && str[i] == ' '){

endpos = i-1;

status--;

for (int j = endpos;j >= startpos;j--) {

res += str[j];

}

res += ' ';

}else{

}

res.erase(res.end()-1,res.end());

cout << res << endl;

}

return 0;

}

请替我问候出题人全家。。。

这个题绝对是良／心／题；为啥你会黄呢？给你个样例吧：
—-watashi-wa-saiko–desu!—-
—-ihsataw-aw-okias–!used—-

上面的－都是空格嗯。。。

HDU 1039 Easier Done Than Said?

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

int main(int argc, char *argv[]) {
	string str;
	while (cin >> str) {
		if (str == "end"){
			break;
		}
		//vowel check
		bool vowelflag = false;
		for (int i = 0;i < str.size();i++) {
			if(str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u'){
				vowelflag = true;
				break;
			}
		}
		bool onajiflag = false;
		char prev = str[0];
		for (int i = 1;i < str.size();i++) {
			if(str[i] == prev){
				if(prev == 'e' || prev == 'o'){
					continue;
				}else {
					onajiflag = true;
					break;
				}
			}
			prev = str[i];
		}
		bool threeflag = false;
		for (int i = 0;i < (int)str.size()-2;i++) {//kengkengkeng
			bool isvowel[3] = {false,false,false};
			for (int j = 0;j <= 2;j++){
			if(str[i+j] == 'a' || str[i+j] == 'e' || str[i+j] == 'i' || str[i+j] == 'o' || str[i+j] == 'u'){
				isvowel[j] = true;
			}
			}
			if((isvowel[0] && isvowel[1] && isvowel[2]) || (!isvowel[0] && !isvowel[1] && !isvowel[2])){
				threeflag = true;
				break;
			}
		}

		//cout << vowelflag << onajiflag << threeflag << endl;
		if(vowelflag && !onajiflag && !threeflag)
		cout << '<' << str << '>' << " is acceptable." << endl;
		else cout << '<' << str << '>' << " is not acceptable." << endl;

	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int main(int argc, char *argv[]) {

string str;

while (cin >> str) {

if (str == "end"){

break;

}

//vowel check

bool vowelflag = false;

for (int i = 0;i < str.size();i++) {

if(str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u'){

vowelflag = true;

break;

}

bool onajiflag = false;

char prev = str[0];

for (int i = 1;i < str.size();i++) {

if(str[i] == prev){

if(prev == 'e' || prev == 'o'){

continue;

}else {

onajiflag = true;

break;

}

prev = str[i];

}

bool threeflag = false;

for (int i = 0;i < (int)str.size()-2;i++) {//kengkengkeng

bool isvowel[3] = {false,false,false};

for (int j = 0;j <= 2;j++){

if(str[i+j] == 'a' || str[i+j] == 'e' || str[i+j] == 'i' || str[i+j] == 'o' || str[i+j] == 'u'){

isvowel[j] = true;

}

if((isvowel[0] && isvowel[1] && isvowel[2]) || (!isvowel[0] && !isvowel[1] && !isvowel[2])){

threeflag = true;

break;

}

//cout << vowelflag << onajiflag << threeflag << endl;

if(vowelflag && !onajiflag && !threeflag)

cout << '<' << str << '>' << " is acceptable." << endl;

else cout << '<' << str << '>' << " is not acceptable." << endl;

}

return 0;

}

c++课后作业系列，但是有坑。

注意看我标kengkengkeng那里，string.size()默认返回的类型是unsigned long，当字符串长度为1时，减去2会发生啥估计大家也都清楚，

HDU 1020 Encoding

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

int main(int argc, char *argv[]) {
	int cnt;
	cin >> cnt;
	while (cnt--) {
		string str;
		cin >> str;
		string res;
		char curr = str[0];
		int occ = 1;
		for (int i = 1;i < str.size();i++) {
			if(str[i] != curr){
				if(occ == 1){

				}else{
					char tmp[5];
					sprintf(tmp,"%d",occ);
					res += tmp;
				}
				res += curr;
				curr = str[i];
				occ = 1;
			}else{
				occ++;
			}
		}
		if(occ == 1){

		}else{
			char tmp[5];
			sprintf(tmp,"%d",occ);
			res += tmp;
		}
		res += curr;
		cout << res << endl;

	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int main(int argc, char *argv[]) {

int cnt;

cin >> cnt;

while (cnt--) {

string str;

cin >> str;

string res;

char curr = str[0];

int occ = 1;

for (int i = 1;i < str.size();i++) {

if(str[i] != curr){

if(occ == 1){

}else{

char tmp[5];

sprintf(tmp,"%d",occ);

res += tmp;

}

res += curr;

curr = str[i];

occ = 1;

}else{

occ++;

}

if(occ == 1){

}else{

char tmp[5];

sprintf(tmp,"%d",occ);

res += tmp;

}

res += curr;

cout << res << endl;

}

return 0;

}

非常非常非常水。连sprintf都放跑了。。。

HDU 1251 统计难题

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

struct trieNode{
    trieNode* child[30];
    int count;
    bool exist;
    trieNode(){
        memset(child, NULL, sizeof(child));
        count = 0;
        exist = false;
    }
} trie,*currNode;


int main(){
    string str;
    bool status = true;
    while (getline(cin,str)) {
        if (str.size() == 0) {
            status = false;
            continue;
        }
        if (status) {
            currNode = &trie;
            for (int i = 0; i < str.size(); i++) {
                if((*currNode).child[str[i]-'a'] == NULL){
                    (*currNode).child[str[i]-'a'] = new trieNode;

                }else{
                    (*currNode).child[str[i]-'a']->count++;
                    if (i == str.size()-1) (*currNode).child[str[i]-'a']->exist = true;
                }
                currNode = (*currNode).child[str[i]-'a'];
            }
        }else{
            currNode = &trie;
            bool flag = false;
            for (int i = 0; i < str.size(); i++) {
                if((*currNode).child[str[i]-'a'] == NULL){
                    break;
                }else{
                    if (i == str.size()-1) {
                        cout << (*currNode).child[str[i]-'a']->count+1<< endl;
                        flag = true;
                    }
                }
                currNode = (*currNode).child[str[i]-'a'];
            }
            if (!flag) {
                cout << 0 << endl;
            }

        }

    }

}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

struct trieNode{

trieNode* child[30];

int count;

bool exist;

trieNode(){

memset(child, NULL, sizeof(child));

count = 0;

exist = false;

}

} trie,*currNode;

int main(){

string str;

bool status = true;

while (getline(cin,str)) {

if (str.size() == 0) {

status = false;

continue;

}

if (status) {

currNode = &trie;

for (int i = 0; i < str.size(); i++) {

if((*currNode).child[str[i]-'a'] == NULL){

(*currNode).child[str[i]-'a'] = new trieNode;

}else{

(*currNode).child[str[i]-'a']->count++;

if (i == str.size()-1) (*currNode).child[str[i]-'a']->exist = true;

}

currNode = (*currNode).child[str[i]-'a'];

}

}else{

currNode = &trie;

bool flag = false;

for (int i = 0; i < str.size(); i++) {

if((*currNode).child[str[i]-'a'] == NULL){

break;

}else{

if (i == str.size()-1) {

cout << (*currNode).child[str[i]-'a']->count+1<< endl;

flag = true;

}

currNode = (*currNode).child[str[i]-'a'];

}

if (!flag) {

cout << 0 << endl;

}

涨姿势了，new开辟的内存空间中变量是没有被初始化的，要自己写一个初始化的constructor才可以，否则就是RERERE。。。

然后Trie的实现方法基本就是这样，指针写法还是比较好弄的，但是以后还要考虑垃圾回收的问题。

POJ 3461 Oulipo

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

vector<int> getNext(char* str){
	int len = strlen(str);
	vector<int> lt;
	lt.push_back(0);
	//cout << 0 << endl;
	for (int i = 1;i < len;i++) {

		if(str[lt[i-1]] == str[i]){
			lt.push_back(lt[i-1]+1);
		}else{
			lt.push_back(0);
		}


		//cout << lt[i] << endl;
	}
	return lt;
}




int main(int argc, char *argv[]) {
	int cnt = 0;
	cin >> cnt;
	while (cnt--) {
		char a[10005],b[1000005];
		scanf(" %s %s",a,b);
		vector<int> lt = getNext(a);
		int lena = strlen(a),lenb = strlen(b);
		int cura = 0,curb = 0,res = 0;
		while(curb < lenb){
			//cout << "^" << curb << "!" << cura << endl;
		while (cura < lena && curb < lenb){
			//cout << "!" << cura << endl;
			if(b[curb] == a[cura]){
				cura++,curb++;
			}else{
				if(cura == 0) curb++;
				else cura = lt[cura-1];
			}
		}
		if (curb >= lenb && cura != lena) break;//failed
		if(cura == lena){//success
			//cout << "get"  << curb << endl;
			res++;

			cura = lt[cura-1];
		}

		}
		cout << res << endl;

	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

vector<int> getNext(char* str){

int len = strlen(str);

vector<int> lt;

lt.push_back(0);

//cout << 0 << endl;

for (int i = 1;i < len;i++) {

if(str[lt[i-1]] == str[i]){

lt.push_back(lt[i-1]+1);

}else{

lt.push_back(0);

}

//cout << lt[i] << endl;

}

return lt;

}

int main(int argc, char *argv[]) {

int cnt = 0;

cin >> cnt;

while (cnt--) {

char a[10005],b[1000005];

scanf(" %s %s",a,b);

vector<int> lt = getNext(a);

int lena = strlen(a),lenb = strlen(b);

int cura = 0,curb = 0,res = 0;

while(curb < lenb){

//cout << "^" << curb << "!" << cura << endl;

while (cura < lena && curb < lenb){

//cout << "!" << cura << endl;

if(b[curb] == a[cura]){

cura++,curb++;

}else{

if(cura == 0) curb++;

else cura = lt[cura-1];

}

if (curb >= lenb && cura != lena) break;//failed

if(cura == lena){//success

//cout << "get" << curb << endl;

res++;

cura = lt[cura-1];

}

cout << res << endl;

}

return 0;

}

在标准KMP的基础上，在匹配完后，继续匹配而不停止，只是给计数器加一下。

第一次自己写KMP，我已逼实。

POJ 2406 Power Strings

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

int main(int argc, char *argv[]) {
	char str[1000005];
	while (scanf(" %s",str) != EOF) {
		int len = strlen(str);
		if(len == 1 && str[0] == '.') break;
		for (int i = 1;i <= len;i++) {
			if (len % i != 0){
				continue;
			}else{
				string t;
				for (int j = 0;j < i;j++) {
					t += str[j];
				}
				int cur = 0;
				bool flag = true;
				while (cur < len) {
					if(!flag) break;
					for (int j = 0;j < i;j++) {
						if(str[cur] == t[j]){
							cur++;
							continue;
						}else{
							flag = false;
							break;
						}
					}
				}
				if(flag) {
					cout << len/i << endl;
					break;
				}
		}
	}
}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int main(int argc, char *argv[]) {

char str[1000005];

while (scanf(" %s",str) != EOF) {

int len = strlen(str);

if(len == 1 && str[0] == '.') break;

for (int i = 1;i <= len;i++) {

if (len % i != 0){

continue;

}else{

string t;

for (int j = 0;j < i;j++) {

t += str[j];

}

int cur = 0;

bool flag = true;

while (cur < len) {

if(!flag) break;

for (int j = 0;j < i;j++) {

if(str[cur] == t[j]){

cur++;

continue;

}else{

flag = false;

break;

}

if(flag) {

cout << len/i << endl;

break;

}

return 0;

}

暴力就行，不用想多了

然后因为是单调性的问题，注意剪枝，不要傻得乎的都判断了。