Pagini recente » Cod sursa (job #911909) | Cod sursa (job #2448341) | Cod sursa (job #407317) | Cod sursa (job #2839395) | Cod sursa (job #2366728)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int sub_string[2000005];
string source, query;
vector<int> oc;
void generate_substring()
{
int querySize = query.size();
int j = 0, i = 1;
while (i < querySize)
{
if (query[i] == query[j])
{
sub_string[i] = j + 1;
i++, j++;
}
else
{
if (j != 0)
j = sub_string[j - 1];
else
i++, sub_string[i] = 0;
}
}
}
void compare()
{
int sourceSize = source.size(), querySize = query.size();
int sourceIndex = 0, queryIndex = 0;
while (sourceIndex < sourceSize)
{
if (source[sourceIndex] == query[queryIndex])
{
if (queryIndex == querySize - 1)
{
oc.push_back(sourceIndex - querySize + 1);
queryIndex = sub_string[queryIndex];
}
else
queryIndex++;
sourceIndex++;
}
else
{
if (queryIndex != 0)
queryIndex = sub_string[queryIndex - 1];
sourceIndex++;
}
}
}
int main()
{
f >> query >> source;
generate_substring();
compare();
cout << oc.size() << '\n';
for (int i = 0; i < oc.size() && i < 1000; i++)
{
cout<<oc[i]<<' ';
}
}