Pagini recente » Cod sursa (job #2966476) | Cod sursa (job #1692314) | Cod sursa (job #1381930) | Monitorul de evaluare | Cod sursa (job #2794792)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int LIM = 2000005;
vector <int> sol;
int lps[LIM];
string a, b;
int main (){
fin>>a>>b;
///precalc longest prefix sufix
int p=1, len=0; lps[0] = 0;
while(p < a.size()){
if(a[p] == a[len])
lps[p++] = ++len;
else{
if(len != 0)
len = lps[len-1];
else
lps[++p] = 0;
}
}
int i=0, j=0;
while(i < b.size()){
if(a[j] == b[i]){
i++;
j++;
}else{
if(j == a.size())
sol.push_back(i-j), j=lps[j-1];
else if(i < b.size() && b[i] != a[j]){
if(j != 0)
j = lps[j-1];
else
i++;
}
}
}
fout<<sol.size()<<"\n";
for(int i=0; i<sol.size(); i++)
fout<<sol[i]<<" ";
return 0;
}