Pagini recente » Cod sursa (job #477719) | Cod sursa (job #2166296) | Cod sursa (job #50923) | Cod sursa (job #1896079) | Cod sursa (job #3257709)
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");
void solve();
int main(){
std::cin.tie(NULL);
std::ios_base::sync_with_stdio(false);
std::string s, pat;
f>>pat>>s;
std::vector<int> lps(pat.size() + 1), res;
int i = 1, len = 0; lps[0] = 0;
while(i < pat.length())
if(pat[i] == pat[len])
lps[i ++] = ++ len;
else
if(len == 0)
lps[i ++] = 0;
else
len = lps[len - 1];
int j = 0, ans = 0;
for(i = 0; i < s.size(); ++i)
if(s[i] == pat[j]){
++j;
if(j == pat.size()){
res.push_back(i - j), j = lps[j - 1];
}
}
else
if(j)
j = lps[j - 1], -- i;
g<<res.size()<<'\n';
for(auto i : res)
g<<i + 1<<' ';
return 0;
}