Pagini recente » Cod sursa (job #1433252) | Cod sursa (job #1081885) | Cod sursa (job #2223052) | Cod sursa (job #1625706) | Cod sursa (job #2259712)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string p, t;
vector <int> sol, pi;
inline int get_pi(char ch, int i){//construim automatul
i = pi[i];
while(i != -1 && p[i] != ch)
i = pi[i];
return i;
}
int main()
{
getline(fi, p);
getline(fi, t);
pi.push_back(-1);
for(int i = 0; i < p.size(); i++)
pi.push_back(get_pi(p[i], i) + 1);
int j = 0;
for(int i = 0; i < t.size(); i++){
if(t[i] != p[j])
j = get_pi(t[i], j);
j++;
if(j == p.size()){
sol.push_back(i + 1 - j);
j = pi[j];
}
}
fo << sol.size() << '\n';
if(sol.size() <= 1000)
for(auto e : sol)
fo << e << ' ';
else
for(int i = 0; i < 1000; i++)
fo << sol[i] << ' ';
fi.close();
fo.close();
return 0;
}