Pagini recente » Cod sursa (job #1659115) | Cod sursa (job #3212168) | Cod sursa (job #1758663) | Cod sursa (job #37210) | Cod sursa (job #3254097)
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int poz[2000005], sol[2000005];
queue<int> out;
void kmp(string& s){
poz[0] = 0;
int j = 0;
for(int i = 1; i < s.size(); ++ i){
if(s[i] == s[j]){
poz[i] = j;
++ j;
}
else{
while(s[i] != s[j] && j != 0){
j = s[j];
}
poz[i] = j;
++ j;
}
}
}
void solve(string& s, string& p){
int j = 0, ans = 0;
for(int i = 0; i < s.size(); ++ i){
if(s[i] == p[j]){
sol[i] = j;
++ j;
}
else{
while(s[i] != p[j] && j != 0){
j = poz[j];
}
sol[i] = j;
++ j;
}
if(j == p.size()){
++ ans;
if(ans <= 1000){
out.push(i - p.size() + 1);
}
-- j;
j = poz[j];
while(s[i] != p[j] && j != 0){
j = poz[j];
}
++ j;
}
}
fout << ans << '\n';
while(!out.empty()){
fout << out.front() << ' ';
out.pop();
}
}
int main()
{
string s1, s2;
fin >> s1 >> s2;
kmp(s1);
solve(s2, s1);
return 0;
}