Pagini recente » Cod sursa (job #216625) | Cod sursa (job #567563) | Cod sursa (job #7781) | Cod sursa (job #489242) | Cod sursa (job #3257710)
#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 + 1), j = lps[j - 1];
}
}
else
if(j)
j = lps[j - 1], -- i;
g<<res.size()<<'\n';
for(int k = 0; k < std::min(1000, (int) res.size()); ++k)
g<<res[k]<<' ';
return 0;
}