Pagini recente » Cod sursa (job #1451907) | Cod sursa (job #1384131) | Cod sursa (job #1295420) | Cod sursa (job #1051723) | Cod sursa (job #2899870)
/// always:
#include <cstdio>
#include <string>
/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
bool home = 1;
using namespace std;
const string TASKNAME="strmatch";
signed main() {
#ifdef INFOARENA
home = 0;
#endif
if(!home) {
freopen((TASKNAME + ".in").c_str(), "r", stdin);
freopen((TASKNAME + ".out").c_str(), "w", stdout);
}else{
freopen ("I_am_iron_man", "r", stdin);
}
string s, t;
cin>>s>>t;
int m=(int)s.size();
int n=(int)t.size();
vector<int> lp(m,0);
int j=0;
for (int i=1;i<m;i++) {
while (j&&s[i]!=s[j]) j=lp[j-1];
if (s[i]==s[j]) j++;
lp[i]=j;
}
int sol=0;
vector<int> inds;
j=0;
for (int i=0;i<n;i++) {
while (j&&t[i]!=s[j]) j=lp[j-1];
if (t[i]==s[j]) j++;
if (j==m) {
sol++;
if(sol<=1000) inds.push_back(i-m+1);
j=lp[j-1];
}
}
cout<<sol<<"\n";
for (auto &i:inds){
cout<<i<<" ";
}
cout<<"\n";
}