Pagini recente » Cod sursa (job #1733718) | Cod sursa (job #607594) | Cod sursa (job #1804540) | Cod sursa (job #1528066) | Cod sursa (job #1925573)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
string a, b;
fin >> a >> b;
vector<int> pos;
unsigned int i = 0, j = 0;
unsigned int aux[a.size()];
aux[0] = 0;
for(i = 1; i < a.size(); i++) {
if(a[j] != a[i]) {
if(j == 0) {
aux[i] = 0;
continue;
}
else {
j = aux[j-1];
i--;
}
}
else {
j++;
aux[i] = j;
}
}
j = 0;
while( i < b.size()) {
if( j == a.size()) {
pos.push_back(i - j);
j = aux[j - 1];
if(pos.size() == 1000)
break;
}
if(a[j] == b[i]){
j++;
i++;
}
else {
if(j == 0)
i++;
else {
j = aux[j];
}
}
}
if(j == a.size())
pos.push_back(i - j);
fout << pos.size() << endl;
for(int p :pos)
fout << p << " ";
return 0;
}