Pagini recente » Cod sursa (job #235683) | Cod sursa (job #852409) | Cod sursa (job #793747) | Cod sursa (job #863855) | Cod sursa (job #2807234)
#include <fstream>
//#include <iostream>
#include <vector>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int cnt = 0, m;
string harta, sir;
vector<int> z;
vector<int> rez;
vector<int> z_function(string s)
{
int n = s.length();
vector<int> z(n);
int left = 0, right = 0;
for(int i = 1; i < n; i++)
{
if (i <= right)
z[i] = min (right - i + 1, z[i-left]);
while (i + z[i] < n & s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > right)
{
left = i;
right = i + z[i] - 1;
}
}
return z;
}
int main()
{
in>>sir;
m = sir.size();
in>>harta;
sir += harta;
z = z_function(sir);
for(int i = 0; i < z.size(); i++)
{
if(z[i] == m)
{
cnt++;
rez.push_back(i - m);
}
}
out<<cnt<<"\n";
for(int i = 0; i < rez.size(); i++)
{
out<<rez[i]<<" ";
}
}