Pagini recente » Cod sursa (job #981253) | Cod sursa (job #2858472) | Cod sursa (job #655521) | Cod sursa (job #2375244) | Cod sursa (job #2188198)
#include <bits/stdc++.h>
using namespace std;
const string fisier = "strmatch";
string a, b;
int urm[2000003], k, cnt;
vector<int> sol;
int main()
{
ifstream fin (fisier+".in");
ofstream fout (fisier+".out");
fin >> a >> b;
k = 0;
urm[0] = 0;
for (int i = 1; i < a.length(); ++i){
while(k > 0 && a[k] != a[i])
k = urm[k-1];
if(a[k] == a[i])
++k;
urm[i] = k;
}
k = 0;
for (int i = 0; i < b.length(); ++i){
while(k > 0 && a[k] != b[i])
k = urm[k-1];
if(a[k] == b[i])
++k;
if(k == a.length()){
++cnt;
if(cnt <= 1000)
sol.push_back(i-k+1);
}
}
fout << cnt << "\n";
for (vector<int>::iterator it = sol.begin(); it != sol.end(); ++it)
fout << *it << " ";
return 0;
}