acwing::acwing831 命名空间参考

1. KMP字符串

更多...

函数
vector< int >	get_next (const string &str)
int	main (istream &cin, ostream &cout)
	TEST (acwing831, case1)
	TEST (acwing831, case2)
	TEST (acwing831, case3)
	TEST (get_next, case1)
	TEST (get_next, case2)
	TEST (get_next, case3)

详细描述

1. KMP字符串

函数说明

get_next()

vector< int > acwing::acwing831::get_next

(

const string &

str

)

在文件 acwing.cpp 第 6821 行定义.

                                                {
            const int n = str.length();
            vector next(n, 0);
            int i = 1;
            int j = 0;
            while(i < n && j < n) {
                if(str[i] == str[j]) {
                    //匹配成功
                    next[i] = j + 1;
                    j++;
                    i++;
                } else {
                    if(j == 0) {
                        //开头就匹配失败
                        i++;
                    } else {
                        //匹配失败，但不在开头
                        j = next[j - 1];
                    }
                }
            }
            return next;
        }

被这些函数引用 main() , 以及 TEST().

main()

int acwing::acwing831::main	(	istream &	cin,
		ostream &	cout
	)

在文件 acwing.cpp 第 6788 行定义.

                                              {
            int n;
            int m;
            string p;
            string s;
            cin >> n >> p >> m >> s;
            const vector<int> next = get_next(p);
            int ip                 = 0;
            int is                 = 0;
            while(ip < n && is < m) {
                if(p[ip] == s[is]) {
                    if(ip == n - 1) {
                        //整串匹配成功
                        cout << is - n + 1 << ' ';
                        ip = next[ip - 1];
                    } else {
                        //当前匹配成功
                        ip++;
                        is++;
                    }
                } else {
                    if(ip == 0) {
                        //开头就匹配失败
                        is++;
                    } else {
                        //匹配失败，但不在开头
                        ip = next[ip - 1];
                    }
                }
            }
            return 0;
        }

引用了 get_next().

被这些函数引用 TEST().

TEST() [1/6]

acwing::acwing831::TEST	(	acwing831	,
		case1
	)

在文件 acwing_test.cpp 第 3136 行定义.

                               {
            istringstream in("3\n"
                             "aba\n"
                             "5\n"
                             "ababa");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("0 2 ", ans);
        }

引用了 main().

TEST() [2/6]

acwing::acwing831::TEST	(	acwing831	,
		case2
	)

在文件 acwing_test.cpp 第 3147 行定义.

                               {
            istringstream in("10\n"
                             "jNNNNjNNNN\n"
                             "30\n"
                             "jNNPw9NNNNnNMANTNHGNjNNNNjNNNN");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("20 ", ans);
        }

引用了 main().

TEST() [3/6]

acwing::acwing831::TEST	(	acwing831	,
		case3
	)

在文件 acwing_test.cpp 第 3158 行定义.

                               {
            istringstream in("7\n"
                             "aabaaaa\n"
                             "11\n"
                             "aabaaabaaaa");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("4 ", ans);
        }

引用了 main().

TEST() [4/6]

acwing::acwing831::TEST	(	get_next	,
		case1
	)

在文件 acwing_test.cpp 第 3169 行定义.

                              {
            const string str  = "ababaa";
            const vector next = {0, 0, 1, 2, 3, 1};
            ASSERT_EQ(next, get_next(str));
        }

引用了 get_next().

TEST() [5/6]

acwing::acwing831::TEST	(	get_next	,
		case2
	)

在文件 acwing_test.cpp 第 3175 行定义.

                              {
            const string str  = "ababaaababaa";
            const vector next = {0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5, 6};
            ASSERT_EQ(next, get_next(str));
        }

引用了 get_next().

TEST() [6/6]

acwing::acwing831::TEST	(	get_next	,
		case3
	)

在文件 acwing_test.cpp 第 3181 行定义.

                              {
            const string str  = "aabaaaa";
            const vector next = {0, 1, 0, 1, 2, 2, 2};
            ASSERT_EQ(next, get_next(str));
        }

引用了 get_next().