Pagini recente » Cod sursa (job #708467) | Cod sursa (job #449701) | Cod sursa (job #1812633) | Cod sursa (job #1160237) | Cod sursa (job #1964988)
#include <iostream>
#include <queue>
#include <stack>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int alf = 52+10;
const int maxS = 2000003;
int prefix[maxS];
vector<int> ans;
int am;
void bfs(string &s) {
int crr = -1;
prefix[0] = -1;
for(int i = 1; i < s.size(); i++) {
while(crr != -1 && s[crr+1] != s[i])
crr = prefix[crr];
if(s[crr+1] == s[i])
crr++;
prefix[i] = crr;
}
}
void dfs(string &s, string &s2) {
int crr = -1;
for(int i = 0; i < s.size(); i++) {
while(crr != -1 && s2[crr+1] != s[i])
crr = prefix[crr];
if(s2[crr+1] == s[i])
crr++;
if(crr+1 == s2.size()) {
am++;
if(ans.size() < 1000)
ans.push_back(i);
}
}
}
int main() {
string a,b;
in >> a >> b;
bfs(a);
dfs(b, a);
out << am << '\n';
for(int i = 0; i < ans.size(); i++)
out << ans[i]-a.size()+1 << " ";
return 0;
}