Pagini recente » Cod sursa (job #463977) | Cod sursa (job #473635) | Cod sursa (job #2536044) | Cod sursa (job #2048747) | Cod sursa (job #2266813)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int getz(string str, int Z[],int len)
{
int n = str.length();
int L, R, k;
int sum= 0;
L = R = 0;
for (int i = 1; i < n; ++i){
if (i > R){
L = R = i;
while (R<n && str[R-L] == str[R]) R++;
Z[i] = R-L;
R--;
}
else{
k = i-L;
if (Z[k] < R-i+1)
Z[i] = Z[k];
else{
L = i;
while (R<n && str[R-L] == str[R])R++;
Z[i] = R-L;
R--;
}
}
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;
}