Pagini recente » Cod sursa (job #2329791) | Cod sursa (job #2375329) | Cod sursa (job #2621459) | Cod sursa (job #2612561) | Cod sursa (job #1166283)
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, t;
queue <int> q;
int m, n, i, k, j, v[2000000];
int main(){
fin >> p >> t;
p.insert(0, " ");
t.insert(0, " ");
m = p.length() - 1;
n = t.length() - 1;
for (i = 2; i <= m; i++){
while (p[k + 1] != p[i] and k > 0)
k = v[k];
if (p[k + 1] == p[i]){
k++;
v[i] = k;
}
}
j = 1; i = 0;
while (j <= n){
if (p[i + 1] == t[j]){
i++;
j++;
if (i == m)
q.push(j - i - 1);//fout << j - i - 1 << " ";
}
else if (i > 0)
i = v[i];
else
j++;
}
fout << q.size() << '\n';
i = 1;
while (!q.empty() and i <= 1000){
fout << q.front() << " ";
q.pop(); i++;
}
fout << '\n';
fin.close();
fout.close();
}