Pagini recente » Cod sursa (job #2028170) | Diferente pentru preoni-2007/runda-2 intre reviziile 20 si 17 | Cod sursa (job #506429) | Cod sursa (job #1878474) | Cod sursa (job #1933890)
#include <bits/stdc++.h>
using namespace std;
vector<int> ret;
char a[2000005];
char b[2000005];
int prefix[2000005];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> a;
int n = strlen(a);
for(int i = n + 1; i > 0; i --) a[i] = a[i - 1];
f >> b;
int m = strlen(b);
for(int i = m + 1; i > 0; i --) b[i] = b[i - 1];
if(n > m) {
g << "0\n";
return 0;
}
int k = 0;
for(int i = 2; i <= n; i ++) {
while(k > 0 && a[k + 1] != a[i])
k = prefix[k];
if(a[k + 1] == a[i]) k ++;
prefix[i] = k;
}
k = 0;
for(int i = 1; i <= m; i ++) {
while(k > 0 && a[k + 1] != b[i])
k = prefix[k];
if(a[k + 1] == b[i]) k ++;
if(k == n) {
ret.push_back(i - n);
}
}
g << ret.size() << "\n";
int lim = min(1000, (int)ret.size());
for(int i = 0; i < lim; i ++) g << ret[i] << " ";
g << "\n";
return 0;
}