Pagini recente » Cod sursa (job #402592) | Cod sursa (job #2625549) | Cod sursa (job #180631) | Cod sursa (job #2425558) | Cod sursa (job #2266827)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int getz(string P, int z[],int len)
{
int n = P.length();
int sum =0;
z[1] = 0;
int l = 0, r = 0;
for (int i = 2; i <= n; ++i) {
if (i <= r) {
z[i] = min(z[i - l + 1], r - i + 1);
}
while (i + z[i] - 1 <= n && P[i + z[i]] == P[z[i] + 1]) {
++z[i];
}
if (i + z[i] - 1 >= r) {
r = i + z[i] -1;
l = i;
}
if(z[i] == len)sum++;
}
return sum;
}
void str(string text, string sch)
{
string imp = sch + "#" + text;
int l = imp.length(),len =sch.length();
int Z[l];
int dim = getz(imp, Z,len);
out<<dim<<endl;
for (int i = 0; i < l; ++i)
{
if (Z[i] == sch.length())
out << i - len -1 << " ";
}
}
int main()
{
string sch,text;
in>>sch>>text;
str(text, sch);
return 0;
}