Pagini recente » Cod sursa (job #1669524) | Cod sursa (job #781511) | Cod sursa (job #1701121) | Cod sursa (job #2935212) | Cod sursa (job #1989255)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
vector<int> Z(string s, const string &pattern)
{
vector<int> ret;
vector<int> z;
if(s.size() < pattern.size())
return ret;
s = pattern + s;
z.resize(s.size());
for(int i = 1; i < s.size() && s[i] == s[i-1]; ++i, ++z[1]);
int dr;
z[0] = -1;
for(int i = 2; i < s.size(); ++i)
{
if(z[i-1] <= 1)
dr = i;
else
dr = i + min(z[1], z[i-1]-1);
while(dr < s.size() && s[dr] == s[dr-i])
++dr;
z[i] = dr - i;
}
for(int i = pattern.size(); i < z.size(); ++i)
if(z[i] >= pattern.size())
ret.push_back(i - pattern.size());
return ret;
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
in >> a >> b;
vector<int> sol = Z(b, a);
out << sol.size() << "\n";
for(int i = 0; i < sol.size() && i < 1000; ++i)
out << sol[i] << " ";
in.close();
out.close();
return 0;
}