Pagini recente » Cod sursa (job #1173891) | Cod sursa (job #2550693) | Borderou de evaluare (job #2051263) | Cod sursa (job #952364) | Cod sursa (job #2480846)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int the = 2000000;
const int bath = 41;
const int thebath = the+bath;
string a, b;
int c[thebath];
void readitup(){
a.reserve(thebath), b.reserve(thebath);
fin >> a >> b;
a.insert(a.begin(), ' ');
b.insert(b.begin(), ' ');
}
void preprocessit(){
int x = 0;
for(int i = 2; i < a.size(); i++){
while(a[i] != a[x+1] && x > 0){
x = c[x];
}
if(a[i] == a[x+1]){
x++;
}
c[i] = x;
}
}
int solol = 0;
vector<int> sol;
void findit(){
int x = 0;
for(int i = 1; i < b.size(); i++){
while(a[x+1] != b[i] && x > 0){
x = c[x];
}
if(a[x+1] == b[i]){
x++;
}
if(x == a.size()-1){
solol++;
if(solol <= 1000){
sol.push_back(i-a.size()+1);
}
}
}
}
int main()
{
readitup();
preprocessit();
findit();
fout << solol << "\n";
for(auto a : sol){
fout << a << " ";
}
return 0;
}