acwing::acwing831_408 命名空间参考

1. KMP字符串

更多...

函数
vector< int >	get_next (string p)
int	main (istream &cin, ostream &cout)
	TEST (acwing831_408, case1)

详细描述

1. KMP字符串

函数说明

get_next()

vector< int > acwing::acwing831_408::get_next

(

string

p

)

在文件 acwing408.cpp 第 589 行定义.

                                       {
            vector<int> next(p.size(), 0);
            for(int i = 1, j = 0; i < p.size(); i++) {
                while(j && p[i] != p[j])
                    j = next[j - 1];
                if(p[i] == p[j])
                    j++;
                next[i] = j;
            }
            return next;
        }

被这些函数引用 main().

main()

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

在文件 acwing408.cpp 第 601 行定义.

                                              {
            int n, m;
            string p, s;
            cin >> n >> p >> m >> s;
            vector<int> next = get_next(p);
            for(int i = 0, j = 0; i < m; i++) {
                while(j && s[i] != p[j])
                    j = next[j - 1];
                if(s[i] == p[j])
                    j++;
                if(j == n) {
                    cout << i - n + 1 << ' ';
                    j = next[j - 1];
                }
            }
            return 0;
        }

引用了 get_next().

被这些函数引用 TEST().

TEST()

acwing::acwing831_408::TEST	(	acwing831_408	,
		case1
	)

在文件 acwing408_test.cpp 第 1081 行定义.

                                   {
            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().