Pagini recente » Cod sursa (job #1293472) | Cod sursa (job #104064) | Cod sursa (job #243314) | Cod sursa (job #2006196) | Cod sursa (job #2016152)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string P, T, S;
int Z[4000005], lengthS;
void ZAlgorithm()
{
int left = 0;
int right = 0;
for(int k = 1; k < S.length(); k++) {
if(k > right)
{
left = right = k;
while(right < S.length() && S[right] == S[right - left])
right++;
Z[k] = right - left;
right--;
} else {
int k1 = k - left;
if(Z[k1] < right - k + 1) {
Z[k] = Z[k1];
} else {
left = k;
while(right < S.length() && S[right] == S[right - left])
right++;
Z[k] = right - left;
right--;
}
}
}
}
int main()
{
fin >> P; fin.get(); fin >> T;
S += P; S += "$"; S += T;
ZAlgorithm();
int np = P.length(), answ = 0;
for (int i = np; i < S.length(); ++i)
if (Z[i] == np)
answ ++;
fout << answ << "\n";
int cnt = 0;
for (int i = np; i < S.length() && cnt != 1000; ++i)
if (Z[i] == np)
fout << i - np - 1 << " ", ++cnt;
return 0;
}