Pagini recente » Cod sursa (job #1620258) | Cod sursa (job #2255476) | Cod sursa (job #399995) | Cod sursa (job #445037) | Cod sursa (job #2080986)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int const lenmax = (int) 2e6;
string s1, s2;
int pre[lenmax];
vector<int> sol;
void precompute(){
pre[0] = 0;
int i = 0;
int j = 1;
while(j < s1.size()) {
if(s1[i] == s1[j]) {
pre[j] = i + 1;
i++;
j++;
} else {
if(0 < i)
i = pre[i - 1];
else {
pre[j] = 0;
j++;
}
}
}
//cout<<s1<<endl;
//for(i = 0;i < s1.size();i ++)
//cout << pre[i];
}
int main() {
in >> s1 >> s2;
precompute();
int i = 0;
int j = 0;
int nsol = 0;
while(j < s2.size()) {
if(s1[i] == s2[j]) {
i++;
j++;
if(i == s1.size()) {
i = pre[i-1];
nsol++;
if(nsol <= 1000)
sol.push_back(j - s1.size());
}
} else {
if(0 < i)
i = pre[i - 1];
else
j++;
}
}
out << nsol << "\n";
for(i = 0; i < nsol;i ++)
out << sol[i] << " ";
return 0;
}