Pagini recente » Cod sursa (job #1622094) | Cod sursa (job #1149609) | Cod sursa (job #1610479) | Cod sursa (job #2325110) | Cod sursa (job #2582625)
#include <string>
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int pi[2000005];
vector<int> aparitii;
int main() {
fin >> a >> b;
int l1 = a.length(), l2 = b.length();
int k = -1;
for(int i = 1; i < l1; i++) {
while(k > -1 && a[i] != a[k+1])
k = pi[k];
if(a[i] == a[k+1]) k++;
pi[i] = k;
}
k = -1;
for(int i = 0; i < l2; i++) {
while(k > -1 && b[i] != a[k+1])
k = pi[k];
if(b[i] == a[k+1]) k++;
if(k == l1-1)
aparitii.push_back(i-l1+1);
}
fout << aparitii.size() << '\n';
for(int i = 0; i < min(1000, int(aparitii.size())); i++)
fout << aparitii[i] << ' ';
}