Pagini recente » Cod sursa (job #2452721) | Cod sursa (job #389864) | Cod sursa (job #2000004) | Cod sursa (job #412835) | Cod sursa (job #2833833)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int DIM = 2e6 + 50;
int len, kmp[ 2 * DIM];
string a, b;
int main (){
fin>>b>>a;
a = " " + b + "$" + a;
kmp[1] = 0;
for(int i=2; i < (int)a.size(); i++){
len = kmp[i-1];
while(a[len+1] != a[i] && len > 0)
len = kmp[len];
if(a[len+1] == a[i])
kmp[i] = len + 1;
else
kmp[i] = 0;
}
int sol = 0;
queue<int> start;
for(int i=(int)b.size()+2; i < (int)a.size(); i++)
if(kmp[i] == (int)b.size()){
sol++;
if(sol <= 1000)
start.push(i - 1 - 2*(int)b.size());
}
fout<<sol<<"\n";
while(!start.empty()){
fout<<start.front()<<" ";
start.pop();
}
return 0;
}