Pagini recente » Cod sursa (job #947144) | Cod sursa (job #2774118) | Cod sursa (job #1140100) | Cod sursa (job #877453) | Cod sursa (job #2723105)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int v[2000005];
vector <int> sol;
string pattern, s;
void prefixsufix()
{
int n = pattern.length(), i = 0;
v[0] = 0;
for(int j = 1; j < n; ++j)
{
while(i != 0 && pattern[i] != pattern[j])
i = v[i - 1];
if(pattern[i] == pattern[j])
++i;
v[j] = i;
}
}
int main()
{
getline(cin, pattern);
getline(cin, s);
prefixsufix();
int n = s.length(), m = pattern.length(), j = 0;
for(int i = 0; i < n; ++i)
{
while(j != 0 && (j >= m || pattern[j] != s[i]))
j = v[j - 1];
if(pattern[j] == s[i])
++j;
if(j == m)
{
sol.push_back(i - m + 1);
}
}
cout << sol.size() << '\n';
for(auto it = sol.begin(); it != sol.end(); ++it)
{
cout << *it << ' ';
}
return 0;
}